공장

어떤 공장이 $0$일차 밤부터 $T$일차 밤까지 가동될 예정이다. 공장의 근무는 매일 낮 시간대와 밤 시간대로 나누어 진행한다. 시간 순서대로 $0$일차 밤, $1$일차 낮, $1$일차 밤, $2$일차 낮, $2$일차 밤, $\cdots$, $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$명의 지원자에 대한 정보가 주어질 때, 근무자를 적절히 고용하여 얻을 수 있는 "(총 생산 이익) $-$ (지급하는 총 임금)"의 최댓값과 그때 고용할 근무자의 목록을 구하라.

• 주어지는 모든 수는 정수이다.
• $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점) 추가 제약 조건 없음.

첫 줄에 두 정수 $N$과 $T$가 공백으로 구분되어 차례대로 주어진다.

그다음 $N$개의 줄에 걸쳐, $N$명의 지원자에 대한 정보가 주어진다. 이 중 $i$ $(1 \le i \le N)$번째 줄에는 $i$번 지원자의 정보를 나타내는 네 정수 $A_i$, $B_i$, $C_i$, $D_i$가 공백으로 구분되어 차례대로 주어진다.

첫 줄에 "(총 생산 이익) $-$ (지급하는 총 임금)"의 최댓값을 출력한다.

그다음 줄에 고용할 근무자의 수를 나타내는 정수 $K$를 출력한다.

그다음 줄에 고용할 근무자 $K$명의 번호를 공백으로 구분하여 임의의 순서로 출력한다. $K = 0$인 경우, 빈 줄을 출력해도 되고, 이 줄을 출력하지 않아도 된다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.