Type: RemoteJudge 1000ms 64MiB

练75.2采购奖品

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

马上又到了一年一度的新年联欢,小明作为班里的班长,负责组织策划新年联欢活动,他决定采购一些奖品奖励积极参与每个项目活动的同学。为了激励更多的人参与活动,需要采购的奖品数目越多越好。班费中可支出的钱数为mm元,现给定商店中nn种可作为奖品的物品的价格和库存数量,怎样才能购得最多的物品数?

输入格式

输入一共n1n+1行:
第一行包含两个正整数mm (1<m100001< m ≤10000)和nn(1<n1001 < n≤100),表示可支出的费用为m元和可供购买的物品有nn种。
接下来的nn行,每行包含两个数(有一个空格分隔),分别表示一种物品的单价aa和库存数量bbaabb均不会超过10001000

输出格式

一个整数,表示最多可以购买的物品数量。

样例

500 6
100 3
20 15
50 10
35 5
5 6
60 2
25