Marathon Ice Hockey

A marathon ice hockey game lasts $M$ minutes. During every minute of the game, exactly six players of Ante's team are on the ice.

Ante brought $N$ players to the tournament. Player $i$ has quality $K_i$ and endurance $I_i$. The endurance is the total number of minutes that player $i$ may spend on the ice during the whole game, and those minutes do not have to be consecutive. If a player is on the ice for $X$ minutes, then rests on the bench, then plays $Y$ more minutes, he has used $X + Y$ minutes of his endurance. No player may ever be on the ice for more minutes than his endurance.

A substitution happens between two consecutive minutes, never inside a minute, and several players may be swapped at the same moment. A player who enters the ice at some moment cannot leave at that same moment, and a player who leaves cannot come back at that same moment.

The quality of the team during one minute is the sum of the qualities of the six players who are on the ice in that minute. $Z$ is the sum of those $M$ values. For example, if the game lasts 3 minutes and the quality of the team is 15 in the first minute, 12 in the second and 14 in the third, then $Z = 15 + 12 + 14 = 41$.

The input always allows at least one schedule that keeps six players on the ice in every minute, that is, $I_1 + I_2 + \dots + I_N \ge 6M$.

Print the largest $Z$ that Ante can reach, together with a schedule that reaches it. Many schedules reach the largest $Z$, so the output section pins down exactly one of them.

Marathon ice hockey has no goalie.

The first line contains the integers $M$ and $N$ ($1 \le M \le 500\,000$, $6 \le N \le 500\,000$), the length of the game in minutes and the number of players Ante brought.

Each of the next $N$ lines contains the integers $K_i$ and $I_i$ ($1 \le K_i \le 100\,000$, $1 \le I_i \le M$), the quality and the endurance of one player. The players are numbered from 1 to $N$ in the order they are given in the input.

The schedule is fixed by the rule below, so exactly one output is accepted.

Sort the players by quality in decreasing order, and players of equal quality by increasing number. Hand out playing time in that order: the next player in the order gets the smaller of his endurance and the number of minutes still unassigned, and $6M$ player-minutes are handed out in total. Once $6M$ minutes are assigned, every remaining player gets 0 minutes. This assignment reaches the largest $Z$, and $Z$ is the sum of $K_i$ multiplied by the playing time of player $i$.

Lay the schedule out in a row of $6M$ cells numbered 1 to $6M$. Take the players whose playing time is at least 1 minute, in the same sorted order, and give each of them a block of consecutive cells as long as his playing time, filling the row from cell 1 without gaps. Cell $c$ belongs to minute $((c - 1) \bmod M) + 1$. Every playing time is at most $M$, so the six cells of one minute hold six different players, and those are the players on the ice in that minute.

The first line of output contains $Z$.

The second line contains the numbers of the six players who are on the ice in minute 1, in increasing order.

The third line contains $B$, the number of substitution lines that follow.

Each of the next $B$ lines contains three integers $X$, $A$ and $C$, meaning that after $X$ minutes of play, player $A$ leaves the ice and player $C$ enters it.

Build the substitution lines this way. For each $X$ from 1 to $M - 1$, let $L$ be the players who are on the ice in minute $X$ but not in minute $X + 1$, sorted in increasing order, and let $E$ be the players who are on the ice in minute $X + 1$ but not in minute $X$, also sorted in increasing order. The two lists have the same length. Pair them by position and print one line per pair, with the groups printed in increasing order of $X$.