您正在计划前往圣彼得堡的旅行。经过一番计算,你估计在圣彼得堡逗留每天要花费 $$$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$$$ $$$L \le l_s$$$ 和 $$$R \ge r_s$$$);
- 您的总利润严格为正且尽可能最大(正式而言,您必须最大化 $$$\sum \limits_{s \in S} p_s - k(R - L + 1)$$$ 的值,并且该值应该为正)。
您可能会认为,无论您选择多少个项目,您仍然有时间和能力参与所有项目,即使它们重叠。
输入
第一行包含两个整数 $$$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$$$ 个项目、第 $$$i$$$ 个项目的结束日期以及如果您选择参与该项目您将获得的金额。
输出
如果不可能计划一次具有严格正利润的旅行,请打印唯一的整数 $$$0$$$。
否则,打印两行。第一行应包含四个整数 $$$p$$$、$$$L$$$、$$$R$$$ 和 $$$m$$$ - 分别是您可以获得的最大利润、旅行的开始日期、旅行的结束日期和您选择完成的项目数量。第二行应包含 $$$m$$$ 不同的整数 $$$s_1$$$、$$$s_2$$$、...、$$$s_{m}$$$ — 您选择完成的项目,以任意顺序列出。如果有多个利润最大的答案,请打印其中任何一个。
示例
输入 #1
4 5 1 1 3 3 3 11 5 5 17 7 7 4
输出 #1
13 3 5 2 3 2
输入 #2
1 3 1 2 5
输出 #2
0
输入 #3
4 8 1 5 16 2 4 9 3 3 24 1 5 13
输出 #3
22 1 5 4 3 2 1 4