P5565. 登岛最大功力

场次：2026年9月23日-非AI方向 · 来源：CodeFun2000 P5565

题目描述

功夫迷小明一心想闯出名声。他所处的世界里藏着一座秘岛：人留在岛上时要按时间扣掉功力，岛上冒出来的异事却能把功力补回来。

一辈子里，上岛和离岛最多各发生两次；只去一趟，或者始终不上岛，也都允许。若第一次进入、离开的时刻记成 $L_1$、$R_1$，第二次进入必须严格晚于第一次离开，也就是 $L_2 > R_1$，两段停留不能叠在一起。

假如时刻 $L$ 上岛、时刻 $R$ 离岛，这一段扣掉的功力是 $(R - L) \times c$，意思是每个时间单位扣 $c$ 点。

秘岛上共有 $p$ 起异事。第 $k$ 起能补上的功力是 $w_k$，它占着闭区间 $[a_k, b_k]$。只有整段都落在同一次停留里面，也就是 $L \le a_k$ 并且 $b_k \le R$，这起异事的功力才算拿到。

结算功力等于拿到的各起异事相加，再减掉停留期间扣掉的部分。各起异事的时段可以互相交叉，也可以完全叠在同一段时间上。

请替小明定下每次上岛和离岛的时刻，使结算功力达到最大。

输入格式

首行两个整数 $p$ 和 $c$。$p$ 表示异事的起数，$c$ 表示留在岛上时每个时间单位要扣的功力。

随后 $p$ 行，每行三个整数，依次是这起异事的开始时刻 $a_k$、结束时刻 $b_k$、功力 $w_k$。

数据范围

• $1 \le p \le 10^4$
• $0 \le w_k, c \le 10^9$
• $1 \le a_k, b_k \le 10^9$
• $a_k \le b_k$

输出格式

第一行输出一个整数，表示能达到的最大结算功力。

后面用一行或两行写出停留的进入时刻和离开时刻。若最优选择是不上岛，这里改写 NA。若好几组停留的结算功力一样大，要输出字典序最小的那一组，并且每一段单独算出来的净功力都必须大于 $0$。有两段时，按进入时刻从早到晚输出。

上岛、离岛的时刻只能从这些异事出现过的时刻里挑。

上岛和离岛允许落在同一个时刻。

示例

示例 1

输入：

2 10
1 2 3
5 6 4

输出：

0
NA

说明：

停留 $[1,2]$ 的结算是 $3 - (2-1)\times 10 = -7$，停留 $[5,6]$ 的结算是 $4 - (6-5)\times 10 = -6$，一次罩住全部的 $[1,6]$ 则是 $7 - (6-1)\times 10 = -43$。每一段都是负数，所以上岛不如不去，答案是 $0$，并写出 NA。

示例 2

输入：

3 3
1 4 20
2 3 5
8 9 12

输出：

25
1,4
8,9

说明：

停留 $[1,4]$ 能罩住前两起，结算为 $20+5-(4-1)\times 3 = 16$。

停留 $[8,9]$ 罩住第三起，结算为 $12-(9-8)\times 3 = 9$。

若改成只留 $[1,9]$，三起都能罩住，但结算只有 $37-(9-1)\times 3 = 13$，不如分成两段的 $16+9 = 25$。

示例 3

输入：

3 4
2 5 30
3 4 6
10 14 5

输出：

24
2,5

说明：

停留 $[2,5]$ 罩住前两起，结算为 $30+6-(5-2)\times 4 = 24$。

停留 $[10,14]$ 的结算是 $5-(14-10)\times 4 = -11$，一次从 $2$ 留到 $14$ 的结算是 $41-(14-2)\times 4 = -7$。这两段都不如只保留 $[2,5]$。