The date of a major marathon ice hockey tournament is approaching. As it is often the case in marathon ice hockey, the game is ~M~ minutes long. On the field (ice) are, as in regular ice hockey, at each given moment, six players from each team. However, a game of marathon ice hockey can last a very long time, so the coaches brought a bunch of players in buses and planes so they can perform substitutions when the players get tired.

One of the coaches is the hero of our story, and his name is Ante. Ante brought ~N~ players to the tournament. For each player, he knows two things: the player quality - ~K~, and the player endurance - ~I~. The player endurance is the total time in minutes that a player can spend playing in the game without getting tired. If the player played for ~X~ minutes, then rested on the bench, then played again for ~Y~ minutes, his total playing time is ~X + Y~. When a player plays a total number of minutes equal to their endurance, he gets tired and can't continue playing, so in that moment someone needs to substitute for him, or he will faint on the ice and end up in the hospital (marathon ice hockey is a dangerous game).

The quality of the team in a given minute of the game is the sum of the quality of that team's players that are currently playing. Ante is not a great coach, so he asked you to come up with the initial six players and the substitute schedule so he can achieve the maximum possible sum of the quality of the team for all the minutes in the game - ~Z~. It is guaranteed that it will always be possible to come up with a schedule such that there are six players in the game in each minute.

For example, if the game lasted for 3 minutes, and if in the first minute the quality of the team was ~15~, in the second ~12~, and in the third ~14~, ~Z~ will be equal to ~15 + 12 + 14 = 41~.

Please note: in marathon ice hockey, there is no goalie, because the game must be interesting!

Input Specification

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

Each of the following ~N~ lines contains two positive integers per player, ~K~ ~(1 \le K \le 100\,000)~ and ~I~ ~(1 \le I \le M)~, the quality and the endurance.

The players are numbered from ~1~ to ~N~, in the order given in the input (the first player's number is ~1~, the second is ~2~, etc.)

Output Specification

The first line of output must contain the maximum possible ~Z~ from the task.

The second line of output must contain exactly six numbers - the numbers of the six players that start the game.

The third line of output must contain the number of substitutions ~B~, that must not exceed ~3N~.

Each of the following ~B~ lines must contain, in order from the earliest to the latest substitute, the information about the substitutes, three numbers per substitute, ~X~ ~(1 \le X < M)~, ~A~ and ~B~, where ~X~ is the number of minutes from the start of the game when the substitute is being done, ~A~ is the number of the player exiting the game and going to the bench, and ~B~ is the number of the player that is entering the game as their substitute.

Multiple substitutions in the same minute are permitted, but a player cannot enter the game, and then exit in the same moment, or vice versa.

If multiple solutions exist, output any.

Sample Input 1

200 6
3 200
4 200
5 200
6 200
7 200
8 200

Sample Output 1

6600
1 2 3 4 5 6
0

Sample Input 2

9 9
10 3
9 3
13 9
5 3
15 9
100 9
3 6
2 6
1 6

Sample Output 2

1260
1 2 3 4 5 6
3
3 1 7
3 2 8
3 4 9

Sample Input 3

3 9
100 3
100 3
100 3
100 3
100 2
100 1
50 1
30 2
1 1

Sample Output 3

1610
1 2 3 4 5 6
2
1 6 8
2 5 7

Sample Explanation

For the first case, no substitutes were needed. The entire team will play the game from start to end.