Description

马拉松冰球锦标赛的日子就要到了。正如马拉松冰球比赛中经常出现的那样,比赛时间是M分钟。和常规的冰球比赛一样,在每一给定时刻,场上两队各有6名球员。然而,一场马拉松冰球比赛可以持续很长时间,所以教练带了一群球员,这样当球员们累了的时候,他们可以进行替换。

其中一个名为Ante的教练是我们故事的主角。Ante带了N个球员参加比赛。对于每一个球员,他知道两个参数:球员的能力值K和耐力值I。耐力值是指球员参赛的最大总时间。假设一个球员先参加X分钟,然后休息,再参加Y分钟,他的总参赛时间就是X+Y。当一个球员的总参赛时间等于其耐力值的时候,他就会感到疲惫,不能继续参赛,所以这个时候,就需要其他人来代替他,否则他会晕倒在赛场上,最终被送进医院(马拉松冰球是一个危险的项目)。

在一个给定时刻,队伍的能力值就是当前参赛队员能力值的总和。Ante并不是一个伟大的教练,所以他要求你拿出最初的六名球员和替补球员的方案,以便他能达到每个时刻队伍能力值总和的可能的最大值Z。保证一定能找到一种方案,使得每个时刻场上都有6名球员。

举个例子,假设比赛时间为3分钟,而第一分钟队伍的能力值是15,第二分钟队伍的能力值是12,第三分钟队伍的能力值是14,Z就等于15+12+14=41。

请注意:在马拉松冰球赛中是没有守门员的,因为比赛必须有趣。

Input

第一行输入两个正整数M和N(1≤M≤500 000,6≤N≤500000),分别表示比赛的持续时间(以分钟为单位),和Ante带领的球员数量。

接下来N行,每行两个正整数K和I(1≤K≤100 000,1≤I≤M),表示每个球员的能力值和耐力值。

球员按照输入顺序,从1到N编号。

Output

第一行包含题目要求的可能的最大值Z。

Sample Input 1
200 6
3 200
4 200
5 200
6 200
7 200
8 200
Sample Output 1
6600
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
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