마라톤 아이스하키

마라톤 아이스하키 경기는 $M$분 동안 이어진다. 경기의 매 분마다 안테 팀에서 정확히 여섯 명이 빙판 위에 있다.

안테는 대회에 선수 $N$명을 데려왔다. $i$번 선수의 능력치는 $K_i$, 체력은 $I_i$이다. 체력은 그 선수가 경기 내내 빙판에서 보낼 수 있는 총 시간(분)이고, 이 시간이 연속일 필요는 없다. 어떤 선수가 $X$분을 뛰고 벤치에서 쉰 다음 다시 $Y$분을 뛰면 체력을 $X + Y$만큼 쓴 것이다. 어떤 선수도 자기 체력보다 많은 시간을 빙판에서 보낼 수 없다.

교체는 연속한 두 분 사이에서만 일어나고 1분 안에서는 일어나지 않는다. 같은 순간에 여러 명을 한꺼번에 교체할 수 있다. 어떤 순간에 들어온 선수가 같은 순간에 나갈 수는 없고, 나간 선수가 같은 순간에 다시 들어올 수도 없다.

한 분 동안 팀의 능력치는 그 분에 빙판에 있는 여섯 명의 능력치 합이다. $Z$는 이 값을 $M$분 전체에 대해 더한 값이다. 예를 들어 경기가 3분 동안 이어지고 팀의 능력치가 첫 분에 15, 둘째 분에 12, 셋째 분에 14라면 $Z = 15 + 12 + 14 = 41$이다.

입력은 항상 매 분 여섯 명을 빙판에 세우는 출전 계획이 하나 이상 존재하도록 주어진다. 즉 $I_1 + I_2 + \dots + I_N \ge 6M$이다.

안테가 얻을 수 있는 가장 큰 $Z$와 그 $Z$를 만드는 출전 계획을 출력한다. 가장 큰 $Z$를 만드는 계획은 여러 가지이므로, 출력 항목에서 그중 하나를 정확히 정해 둔다.

마라톤 아이스하키에는 골리가 없다.

첫 줄에 경기 길이 $M$과 안테가 데려온 선수 수 $N$이 주어진다 ($1 \le M \le 500\,000$, $6 \le N \le 500\,000$).

다음 $N$개 줄에는 선수 한 명의 능력치 $K_i$와 체력 $I_i$가 주어진다 ($1 \le K_i \le 100\,000$, $1 \le I_i \le M$). 선수 번호는 입력에 주어진 순서대로 1번부터 $N$번까지이다.

출전 계획은 아래 규칙으로 하나만 정해지므로, 정답으로 인정하는 출력도 하나뿐이다.

선수를 능력치가 큰 순서로 정렬하고, 능력치가 같으면 번호가 작은 선수를 앞에 둔다. 이 순서대로 출전 시간을 나눠 준다. 앞에서부터 각 선수는 자기 체력과 아직 배정하지 않은 시간 중 작은 값을 받고, 전체로는 $6M$분을 배정한다. $6M$분을 모두 배정하면 남은 선수는 0분을 받는다. 이 배정이 가장 큰 $Z$를 만들며, $Z$는 각 선수의 $K_i$에 그 선수의 출전 시간을 곱해 모두 더한 값이다.

이제 1번부터 $6M$번까지 번호를 붙인 칸 한 줄에 계획을 배치한다. 출전 시간이 1분 이상인 선수를 위 정렬 순서대로 놓고, 1번 칸부터 빈칸 없이 각 선수에게 출전 시간만큼 연속한 칸을 준다. $c$번 칸은 $((c - 1) \bmod M) + 1$번째 분에 해당한다. 모든 출전 시간이 $M$ 이하이므로 한 분에 해당하는 여섯 칸에는 서로 다른 여섯 선수가 들어가고, 이들이 그 분에 빙판에 있는 선수이다.

첫 줄에 $Z$를 출력한다.

둘째 줄에 1번째 분에 빙판에 있는 여섯 선수의 번호를 번호가 작은 순서로 출력한다.

셋째 줄에 뒤이어 출력할 교체 줄의 개수 $B$를 출력한다.

다음 $B$개 줄에는 각각 세 정수 $X$, $A$, $C$를 출력한다. 경기 시작 후 $X$분이 지난 순간에 $A$번 선수가 빙판에서 나가고 $C$번 선수가 들어온다는 뜻이다.

교체 줄은 다음과 같이 만든다. $X = 1$부터 $M - 1$까지 각각에 대해, $X$번째 분에는 빙판에 있고 $X + 1$번째 분에는 없는 선수를 번호가 작은 순서로 모아 목록 $L$을 만들고, $X + 1$번째 분에는 있고 $X$번째 분에는 없는 선수를 같은 방식으로 모아 목록 $E$를 만든다. 두 목록의 길이는 같다. 같은 자리끼리 짝지어 한 줄씩 출력하고, $X$가 작은 것부터 출력한다.