一场大型马拉松冰球锦标赛即将举行。正如马拉松冰球比赛中常见的那样，整场比赛将持续 $M$ 分钟。在任何给定的时刻，场上（冰面）上和正规冰球比赛一样，每队都有六名队员。然而，一场马拉松冰球比赛可能会持续非常长的时间，因此教练们用大巴和飞机带来了大批队员，以便在队员疲劳时进行轮换。

我们故事的主角是其中一位教练，名叫 Ante。Ante 为这次锦标赛带来了 $N$ 名队员。对于每位队员，他知道两件事：队员的水平 $K$ 和队员的耐力 $I$。队员的耐力是指该队员在不感到疲劳的情况下，在比赛中能够上场比赛的总时间（以分钟为单位）。如果一名队员上场了 $X$ 分钟，然后在替补席上休息，之后再次上场 $Y$ 分钟，那么他的总上场时间就是 $X + Y$。当一名队员的总上场时间达到其耐力 $I$ 时，他就会感到疲劳并无法继续比赛，此时必须立刻有人替换他，否则他会在冰面上晕倒并被送往医院（马拉松冰球是一项危险的运动）。

在比赛的某一分钟内，队伍的水平是当前场上六名队员水平的总和。Ante 并不是一个出色的教练，因此他请求你帮他确定初始上场的六名队员以及后续的替补方案，以便使整场比赛中所有分钟的队伍水平总和 $Z$ 达到最大。保证总是存在一种方案，使得在比赛的每一分钟内场上都有六名队员。

例如，如果比赛持续 3 分钟，且第一分钟队伍水平为 15，第二分钟为 12，第三分钟为 14，则 $Z$ 将等于 $15 + 12 + 14 = 41$。

请注意：在马拉松冰球中没有守门员，因为比赛必须足够精彩！

输入格式

输入的第一行包含两个正整数 $M$ 和 $N$（$1 \le M \le 500\,000$，$6 \le N \le 500\,000$），分别表示以分钟为单位的比赛持续时间和 Ante 带来的队员人数。

接下来的 $N$ 行，每行包含两个正整数，表示每位队员的水平 $K$（$1 \le K \le 100\,000$）和耐力 $I$（$1 \le I \le M$）。

队员按输入中给出的顺序从 $1$ 到 $N$ 进行编号（第一位队员的编号为 1，第二位为 2，依此类推）。

输出格式

输出的第一行必须包含任务中可能达到的最大 $Z$。

第二行必须包含恰好六个整数——开始比赛的六名队员的编号。

第三行必须包含替换次数 $B$，该次数不能超过 $3 \times N$。

接下来的 $B$ 行，必须按照替换发生的时间从早到晚的顺序，包含每次替换的信息。每次替换包含三个数 $X$（$1 \le X < M$）、$A$ 和 $B$，其中 $X$ 表示从比赛开始起经过的分钟数（即进行替换的时刻），$A$ 是下场前往替补席的队员编号，$B$ 是上场替换他的队员编号。

允许在同一分钟内进行多次替换，但一名队员不能在同一时刻既上场又下场，反之亦然。

如果存在多种解决方案，输出其中任意一种即可。

样例

输入格式 1

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

输出格式 1

6600
1 2 3 4 5 6
0

说明

不需要进行任何替换，整支队伍将从头到尾完成比赛。

输入格式 2

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

输出格式 2

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

输入格式 3

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

输出格式 3

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