Trip to Saint Petersburg

3000ms

524288K

Description:

You are planning your trip to Saint Petersburg. After doing some calculations, you estimated that you will have to spend $$$k$$$ rubles each day you stay in Saint Petersburg — you have to rent a flat, to eat at some local cafe, et cetera. So, if the day of your arrival is $$$L$$$, and the day of your departure is $$$R$$$, you will have to spend $$$k(R - L + 1)$$$ rubles in Saint Petersburg.

You don't want to spend a lot of money on your trip, so you decided to work in Saint Petersburg during your trip. There are $$$n$$$ available projects numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th of them lasts from the day $$$l_i$$$ to the day $$$r_i$$$ inclusive. If you choose to participate in the $$$i$$$-th project, then you have to stay and work in Saint Petersburg for the entire time this project lasts, but you get paid $$$p_i$$$ rubles for completing it.

Now you want to come up with an optimal trip plan: you have to choose the day of arrival $$$L$$$, the day of departure $$$R$$$ and the set of projects $$$S$$$ to participate in so that all the following conditions are met:

your trip lasts at least one day (formally, $$$R \ge L$$$);
you stay in Saint Petersburg for the duration of every project you have chosen (formally, for each $$$s \in S$$$ $$$L \le l_s$$$ and $$$R \ge r_s$$$);
your total profit is strictly positive and maximum possible (formally, you have to maximize the value of $$$\sum \limits_{s \in S} p_s - k(R - L + 1)$$$, and this value should be positive).

You may assume that no matter how many projects you choose, you will still have time and ability to participate in all of them, even if they overlap.

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le k \le 10^{12}$$$) — the number of projects and the amount of money you have to spend during each day in Saint Petersburg, respectively.

Then $$$n$$$ lines follow, each containing three integers $$$l_i$$$, $$$r_i$$$, $$$p_i$$$ ($$$1 \le l_i \le r_i \le 2\cdot10^5$$$, $$$1 \le p_i \le 10^{12}$$$) — the starting day of the $$$i$$$-th project, the ending day of the $$$i$$$-th project, and the amount of money you get paid if you choose to participate in it, respectively.

Output:

If it is impossible to plan a trip with strictly positive profit, print the only integer $$$0$$$.

Otherwise, print two lines. The first line should contain four integers $$$p$$$, $$$L$$$, $$$R$$$ and $$$m$$$ — the maximum profit you can get, the starting day of your trip, the ending day of your trip and the number of projects you choose to complete, respectively. The second line should contain $$$m$$$ distinct integers $$$s_1$$$, $$$s_2$$$, ..., $$$s_{m}$$$ — the projects you choose to complete, listed in arbitrary order. If there are multiple answers with maximum profit, print any of them.

Sample Input:

Sample Output:

13 3 5 2
3 2

Sample Input:

1 3
1 2 5

Sample Output:

Sample Input:

Sample Output:

22 1 5 4
3 2 1 4

Informação

Provedor Codeforces

Código CF1250C