Background

qwq很喜欢玩CSGO（反恐精英：全球攻势）。
有一次她打竞技，上去就是Rush B。

可惜，qwq一下子遇到了\(n\)个敌人，她拿着一把沙鹰不知所措。

她一下子打不死敌人（因为敌人太多？？），眼看她就要死了
但她也有能力（骚走位）活到射光她当前的弹匣（\(g\)颗子弹）。她想在死之前，对敌方造成最多的伤害。

Description

qwq能活着射出g颗子弹，有n个敌人。
每个敌人的能力和生命值都不同，qwq对每个敌人（如果选择攻击）需要射出\(w(i)\)颗子弹，能造成\(s(i)\)点伤害（只能造成一次）。
死之前弹匣可以是有子弹的（不一定需要射出全部的\(g\)颗子弹）

Format

Input

第一行有两个数，当前弹匣子弹数\(g (1 \le g \le 1000)\)，敌人数\(n (1 \le n \le 1000)\)
接下来有\(n\)行，第\(i(1 \le i \le n)\)行有两个数，\(w(i) (1 \le w(i) \le 1000)\)和\(s(i) (1 \le s(i) \le 10000)\)

Output

能对敌人造成的一共最多的伤害总和

Sample 1

Input

5 5
1 69
1 12
3 79
3 100
2 32

Output

181

Limitation

1s, 256MiB for each test case.

Hint

Source

czf