题目描述

某校庆祝元旦需要采购一些瓜子在联欢会上食用，学校给了固定资金n元让小蓝去超市采购瓜子，且要求采购最多的瓜子。
到了超市发现有m种瓜子，且都是成袋售卖。小蓝这下为难了，不知道如何才能用固定资金采购最多的瓜子。
在给出每种瓜子每袋的价格、每袋的重量，请你帮助小蓝计算下用n元最多能采购多少瓜子。
例如：
给定的资金n为80元，瓜子种类m为2种：
第一种瓜子每袋18元，每袋10千克；
第二种瓜子每袋30元，每袋20千克；
用80元资金最多可以买50千克瓜子（买2袋第二种，1袋第一种的，总重量50千克，使用资金78元）。

输入格式

第一行输入两个正整数 $n,m$（以空格分隔），分别表示预算与瓜子种类数。
接下来 $m$ 行，每行输入两个正整数 $p_i,k_i$（以空格分隔），分别表示第 $i$ 种瓜子每袋价格与每袋重量。

输出格式

输出一个正整数，表示在预算不超过 $n$ 的前提下，最多能采购到的瓜子总重量（千克）。

样例输入输出

样例输入1

80 2
18 10
30 20

样例输出1

50

数据范围与测试点说明

• $1\le n\le 1000$；
• $1\le m\le 30$；
• $1<p_i<101$；
• $1<k_i<101$。

时间限制与内存限制

• 时间限制：$1$ 秒
• 内存限制：$1024$ KiB