题目描述

某工厂计划从第 $0$ 天夜间运行到第 $T$ 天夜间。工厂每天的工作分为白天时段和夜间时段。按时间顺序，共分为第 $0$ 天夜间、第 $1$ 天白天、第 $1$ 天夜间、第 $2$ 天白天、第 $2$ 天夜间、……、第 $T$ 天白天、第 $T$ 天夜间，共 $2T+1$ 个时段。每个白天进行日间生产，每个夜间进行夜间警戒。

为了使工厂运行，需要从 $N$ 名应聘者中选出并雇用若干名员工。第 $i$（$1 \le i \le N$）名应聘者的熟练度为 $A_i$，贡献度为 $B_i$，且所有应聘者的熟练度互不相同。若雇用第 $i$ 名应聘者，则该员工会在第 $D_i-1$ 天夜间、第 $D_i$ 天白天和第 $D_i$ 天夜间这三个时段工作，并获得基本工资 $C_i$。也就是说，每名被雇用的员工会参加两次夜间警戒和一次日间生产。

每个时段的工作按如下方式进行：将该时段工作的所有员工按照熟练度从小到大排成一列，再从队首开始依次两两配对。也就是说，如果共有 $2k$ 名员工，则对于每个整数 $j$（$1 \le j \le k$），队列中的第 $2j-1$ 人与第 $2j$ 人组成一组。

所有工作都必须以两人一组的形式进行。因此，必须选择员工，使得每个时段工作的人数均为偶数。允许某个时段没有员工工作，此时该时段不会进行任何工作。

每一组员工会根据所执行的工作产生如下结果：

• 日间生产：白天，每组员工运行一条生产线制造产品，并改变工厂的总生产利润。具体而言，若熟练度满足 $A_x>A_y$ 的第 $x$、第 $y$ 名应聘者组成一组，则总生产利润增加 $B_x-B_y$。请注意，这个值可能为负数。
• 夜间警戒：夜间，每组员工巡查工厂内部，并获得夜间补贴。具体而言，若熟练度满足 $A_x>A_y$ 的第 $x$、第 $y$ 名应聘者组成一组，则两人合计获得 $A_x-A_y$ 的夜间补贴。

工厂开始运行前（第 $0$ 天夜间之前），工厂的总生产利润为 $0$。

工厂支付的总工资等于所有被雇用员工的基本工资之和，加上所有夜间支付的夜间补贴之和。

给定 $N$ 名应聘者的信息，请合理选择要雇用的员工，求可获得的“（总生产利润）$-$（支付的总工资）”的最大值，并输出此时雇用的员工名单。

输入格式

第一行依次给出两个以空格分隔的整数 $N$ 和 $T$。

接下来的 $N$ 行给出 $N$ 名应聘者的信息。其中第 $i$（$1 \le i \le N$）行依次给出四个以空格分隔的整数 $A_i,B_i,C_i,D_i$，表示第 $i$ 名应聘者的信息。

输出格式

第一行输出“（总生产利润）$-$（支付的总工资）”的最大值。

第二行输出要雇用的员工人数 $K$。

第三行以任意顺序输出 $K$ 名要雇用员工的编号，编号之间以空格分隔。当 $K=0$ 时，可以输出空行，也可以不输出这一行。

如果存在多种可行输出，输出其中任意一种均视为正确。

6 2
21 0 1 1
13 25 0 2
22 20 3 2
20 5 2 2
4 23 0 2
25 16 8 1

7
4
1 3 4 6

5 2
40 23 10 1
59 22 2 2
32 7 10 2
52 30 0 1
38 10 3 1

0
0

12 3
6 19 4 2
32 0 1 3
12 0 4 3
25 7 0 2
35 15 5 1
28 25 5 2
19 27 3 3
30 13 3 2
1 24 5 3
20 11 0 2
2 1 5 2
24 28 3 2

20
8
1 3 4 6 7 10 11 12

提示

样例 1 解释

雇用在第 $1$ 天白天工作的第 $1$、第 $6$ 名应聘者，以及在第 $2$ 天白天工作的第 $3$、第 $4$ 名应聘者是最优的。

• 第 $1$ 天白天，第 $1$ 名和第 $6$ 名员工组成一组，总生产利润增加 $B_6-B_1=16$。
• 第 $2$ 天白天，第 $4$ 名和第 $3$ 名员工组成一组，总生产利润增加 $B_3-B_4=15$。

因此，总生产利润为 $16+15=31$。

• 第 $0$ 天夜间，第 $1$ 名和第 $6$ 名员工组成一组，支付 $A_6-A_1=4$ 的夜间补贴。
• 第 $1$ 天夜间，四名员工全部工作。按熟练度顺序排列为第 $4$ 名（$A_4=20$）、第 $1$ 名（$A_1=21$）、第 $3$ 名（$A_3=22$）、第 $6$ 名（$A_6=25$）。第 $4$ 名与第 $1$ 名、第 $3$ 名与第 $6$ 名分别组成一组。该夜支付的夜间补贴为 $(A_1-A_4)+(A_6-A_3)=1+3=4$。
• 第 $2$ 天夜间，第 $3$ 名和第 $4$ 名员工组成一组，支付 $A_3-A_4=2$ 的夜间补贴。

因此，夜间补贴总额为 $4+4+2=10$。

支付的总工资为基本工资 $1+3+2+8=14$ 加夜间补贴 $10$，共计 $24$；最终“（总生产利润）$-$（支付的总工资）”为 $31-24=7$。

请注意，在此样例中，第 $1$ 天白天和第 $1$ 天夜间的分组并不相同。

样例 2 解释

不雇用任何人是最优的。

限制条件

• 给出的所有数均为整数。
• $1 \le T \le N \le 500$
• 对于每个整数 $i$（$1 \le i \le N$），$0 \le A_i \le 1\,000$。
• 对于每个整数 $i$（$1 \le i \le N$），$0 \le B_i \le 1\,000$。
• 对于每个整数 $i$（$1 \le i \le N$），$0 \le C_i \le 1\,000$。
• 对于每个整数 $i$（$1 \le i \le N$），$1 \le D_i \le T$。
• $A_1,A_2,\cdots,A_N$ 两两不同。

子任务

1. （$13$ 分）$N \le 20$。
2. （$14$ 分）$T=1$。
3. （$20$ 分）$T \le 10$。
4. （$22$ 分）对于每个整数 $d$（$1 \le d \le T$），满足 $D_i=d$ 的应聘者不超过 $8$ 名。
5. （$31$ 分）没有额外限制。