Problem Description

A factory plans to operate from the night of day $0$ to the night of day $T$. Each day is divided into a daytime period and a nighttime period. In chronological order, the periods are: night of day $0$, daytime of day $1$, night of day $1$, daytime of day $2$, night of day $2$, $\cdots$, daytime of day $T$, night of day $T$, for a total of $2T+1$ periods. During each daytime period, daytime production is performed, and during each nighttime period, nighttime security is performed.

To run the factory, it is necessary to choose and hire some employees from $N$ applicants. The $i$-th applicant ($1 \le i \le N$) has skill level $A_i$ and contribution value $B_i$, and all applicants have distinct skill levels. If the $i$-th applicant is hired, this employee will work in exactly three periods: the night of day $D_i-1$, the daytime of day $D_i$, and the night of day $D_i$, and will receive a base salary $C_i$. That is, each hired employee participates in two nighttime security shifts and one daytime production shift.

Work in each period is conducted as follows: all employees working in that period are sorted in increasing order of skill level to form a line, then starting from the front, they are paired up sequentially. That is, if there are $2k$ employees in total, then for each integer $j$ ($1 \le j \le k$), the $(2j-1)$-th person and the $(2j)$-th person in the line form a pair.

All work must be done in pairs of two. Therefore, employees must be chosen so that the number of employees working in every period is even. It is allowed that no one works in some period; in that case, no work is performed in that period.

Each pair of employees produces the following results depending on the type of work:

• Daytime production: During the day, each pair operates a production line to manufacture products, changing the factory’s total production profit. Specifically, if applicants $x$ and $y$ form a pair with skill levels satisfying $A_x>A_y$, then the total production profit increases by $B_x-B_y$. Note that this value may be negative.
• Nighttime security: During the night, each pair patrols inside the factory and receives a night allowance. Specifically, if applicants $x$ and $y$ form a pair with skill levels satisfying $A_x>A_y$, then the two of them receive a total night allowance of $A_x-A_y$.

Before the factory starts operating (before the night of day $0$), the total production profit is $0$.

The factory’s total wage payment equals the sum of base salaries of all hired employees, plus the sum of all night allowances paid during all nights.

Given the information of the $N$ applicants, choose whom to hire to maximize “(total production profit) $-$ (total wages paid)”, and output the list of hired employees in this case.

Input Format

The first line contains two integers $N$ and $T$ separated by spaces.

The next $N$ lines give the information of the $N$ applicants. The $i$-th line ($1 \le i \le N$) contains four integers $A_i,B_i,C_i,D_i$ separated by spaces, describing the $i$-th applicant.

Output Format

The first line outputs the maximum value of “(total production profit) $-$ (total wages paid)”.

The second line outputs the number of employees to hire, $K$.

The third line outputs, in any order, the indices of the $K$ employees to hire, separated by spaces. When $K=0$, you may output an empty line, or you may omit this line.

If there are multiple feasible outputs, any one of them is considered correct.

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

Hint

Sample 1 Explanation

It is optimal to hire applicants $1$ and $6$ who work in the daytime of day $1$, and applicants $3$ and $4$ who work in the daytime of day $2$.

• Daytime of day $1$: employee $1$ and employee $6$ form a pair, so the total production profit increases by $B_6-B_1=16$.
• Daytime of day $2$: employee $4$ and employee $3$ form a pair, so the total production profit increases by $B_3-B_4=15$.

Thus, the total production profit is $16+15=31$.

• Night of day $0$: employee $1$ and employee $6$ form a pair, and a night allowance of $A_6-A_1=4$ is paid.
• Night of day $1$: all four employees work. Sorted by skill level, the order is employee $4$ ($A_4=20$), employee $1$ ($A_1=21$), employee $3$ ($A_3=22$), employee $6$ ($A_6=25$). Employee $4$ pairs with employee $1$, and employee $3$ pairs with employee $6$. The night allowance paid that night is $(A_1-A_4)+(A_6-A_3)=1+3=4$.
• Night of day $2$: employee $3$ and employee $4$ form a pair, and a night allowance of $A_3-A_4=2$ is paid.

Thus, the total night allowance is $4+4+2=10$.

The total wages paid are base salaries $1+3+2+8=14$ plus night allowances $10$, totaling $24$. Therefore, the final value of “(total production profit) $-$ (total wages paid)” is $31-24=7$.

Note that in this sample, the pairings in the daytime of day $1$ and the night of day $1$ are not the same.

Sample 2 Explanation

Hiring no one is optimal.

Constraints

• All given numbers are integers.
• $1 \le T \le N \le 500$.
• For each integer $i$ ($1 \le i \le N$), $0 \le A_i \le 1\,000$.
• For each integer $i$ ($1 \le i \le N$), $0 \le B_i \le 1\,000$.
• For each integer $i$ ($1 \le i \le N$), $0 \le C_i \le 1\,000$.
• For each integer $i$ ($1 \le i \le N$), $1 \le D_i \le T$.
• $A_1,A_2,\cdots,A_N$ are pairwise distinct.

Subtasks

1. ($13$ points) $N \le 20$.
2. ($14$ points) $T=1$.
3. ($20$ points) $T \le 10$.
4. ($22$ points) For each integer $d$ ($1 \le d \le T$), there are at most $8$ applicants with $D_i=d$.
5. ($31$ points) No additional constraints.

Translated by ChatGPT 5