Description

小B一到市场,傻眼了,卖物资的老板告诉小B这些货是不能拆开卖,要买就只能全部都买了,小B回去和后勤的boss报告,后勤的boss也很尴尬,只能说,钱就那么多,尽量多买点吧.
小B这回就真不知道该咋办了,但是呢,小B还有绝招---求助,女孩子到哪都不缺人帮助滴~.

Input

小B拿到钱n(1~1000).
物资总类数m(1~16).
接下来m行,每行两个正整数,该类物资单价a和总数b.

Output

能购买的最多物资.

Sample Input

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

Sample Output

40

HINT

Source

NBU OJ