Description

XXX上山去采药。XXX有一个容量为$m (1<=m<=1000)$的背包，他所采集的药材的总重量不能大于背包的容量。已知共有$n(1<=n<=1000 )$种药材，每种药材都有无限多，并且知道每种药材的重量$w(1<=w<=m)$及价值$v(1<=v<=100000)$，如何选择，才能使得采到的药材的总价值最大？

Input

第1行为两个整数 $m$ 和 $n$，分别为背包的容量及药材的种数。 第 $2$ 至 $n+1$ 行每行两个整数 $w$ 和 $v$ ，分别表示每种药材的重量及价值。

Output

能采到的药材的最大总价值

Samples

100 5
77 92
33 50
34 60
50 46
99 161

161