CF1250C.Trip to Saint Petersburg

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.

你正在规划前往圣彼得堡的旅行。经过一些计算，你估计在圣彼得堡停留的每一天都需要花费 $k$ 卢布——例如租住公寓、在当地咖啡馆用餐等。因此，若你的抵达日期为 $L$，离开日期为 $R$，则你在圣彼得堡的总花费为 $k(R - L + 1)$ 卢布。

你不想在旅行上花费过多金钱，因此决定在旅行期间于圣彼得堡工作。目前共有 $n$ 个可选项目，编号从 $1$ 到 $n$；其中第 $i$ 个项目的时间跨度为从第 $l_i$ 天到第 $r_i$ 天（含端点）。若你选择参与第 $i$ 个项目，则你必须在整个项目持续期间都留在圣彼得堡并工作，但完成该项目后你将获得 $p_i$ 卢布的报酬。

现在，你需要制定一个最优旅行计划：选择抵达日期 $L$、离开日期 $R$，以及参与的项目集合 $S$，使得满足以下所有条件：

• 旅行至少持续一天（形式化地，$R \ge L$）；
• 对于你所选的每个项目 $s \in S$，你均需在圣彼得堡停留至其整个持续期间（形式化地，对每个 $s \in S$，均有 $L \le l_s$ 且 $R \ge r_s$）；
• 你的总利润严格为正，且尽可能大（形式化地，需最大化 $\sum \limits_{s \in S} p_s - k(R - L + 1)$ 的值，且该值必须大于 $0$）。

你可以假设：无论你选择多少个项目，你总有足够的时间和能力参与所有选定的项目，即使它们的时间段存在重叠。

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.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2\cdot10^5$，$1 \le k \le 10^{12}$），分别表示项目的数量以及你在圣彼得堡每天需要花费的金额。

接下来是 $n$ 行，每行包含三个整数 $l_i$、$r_i$、$p_i$（$1 \le l_i \le r_i \le 2\cdot10^5$，$1 \le p_i \le 10^{12}$），分别表示第 $i$ 个项目的起始日期、结束日期，以及若你选择参与该项目所能获得的报酬金额。

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.

如果无法规划一次严格正收益的旅行，则仅输出整数 $0$。

否则，输出两行。第一行应包含四个整数 $p$、$L$、$R$ 和 $m$ —— 分别表示你能获得的最大收益、旅行的起始天数、旅行的结束天数以及你选择完成的项目数量。第二行应包含 $m$ 个互不相同的整数 $s_1$、$s_2$、...、$s_{m}$ —— 表示你选择完成的项目，顺序任意。若存在多个具有最大收益的方案，输出其中任意一个即可。