Description

钱终于收齐了(但是小B似乎把奖励忘了),小B总算可以清静的过一天了,于是便跑去图书馆看书.但是由于还未专业分流,而且对钱途很迷茫,所以他决定只要是书就看,但是呢图书馆的书那么多,所以他决定挑几个书架看(小B能一目万行),但是她又想看很多的书,请帮她算算最多能看多少书(最后一本书不一定要看完)。假设有n(0<n<=16)个书架,看同一个书架上的书,耗时相等。

Input

小B看书的时间T. 书架数n. 接下来n行,每行两个正整数,在看一本书花费的时间t和该书架的书的总数m.

Output

小B最多能看的书的数量.

Sample Input

100
5
1 10
2 10
3 10
4 10
5 10

Sample Output

40

HINT

Source

NBU OJ