题目描述

某校为庆祝元旦，准备采购一些瓜子在联欢会上食用。

学校给了固定的资金 $N$（$1 \le N \le 1000$）元让小蓝去超市采购瓜子，且要求采购到最多的瓜子。到了瓜子有 $M$ （$1 \le M \le 30$） 个品种，瓜子都是以袋为单位售卖。小蓝这下子为难了，不知道如何才能以固定的钱买到最多的瓜子。

给出每种瓜子每袋的价格和重量，请你帮助小蓝计算 $N$ 元最多能买多重的瓜子。

输入格式

第一行 2 个数字，$N$ 和 $M$，分别代表采购瓜子的资金限额，以及瓜子的种类。

接下来 $M$ 行，每行 $2$ 个数字 $P_i$ 和 $W_i$ ，代表第 $i$ 种瓜子每袋的价格和重量。

输出格式

最大采购到的最大重量。

样例

80 2
18 10
30 20

50

样例解释
80 元，2 种瓜子。第 1 种，每袋 18 元 10 千克，买 1 袋；第 2 种，每袋 30 元 20 千克，买 2 袋，总价 78 元，重量 50 千克。