题目描述

某校庆祝元旦需要采购一些瓜子在联欢会上食用，学校给了固定资金 $n$ 元让小蓝去超市采购瓜子，且要求采购最多的瓜子。到了超市发现有 $m$ 种瓜子，且都是成袋售卖。小蓝这下为难了，不知道如何才能用固定资金采购最多的瓜子。

在给出每种瓜子每袋的价格、每袋的重量，请你帮助小蓝计算下用 $n$ 元最多能采购多少瓜子。

例如:

给定的资金$n$为80元，瓜子种类$m$为2种:

第一种瓜子每袋 18 元，每袋 10 千克;

第二种瓜子每袋 30 元，每袋 20 千克:

用80 元资金最多可以买 50 千克瓜子(买2 袋第二种，1袋第一种的，总重量 50 千克，使用资金 78元)

输入

第一行输入两个正整数$n$和$m$，用一个空格隔开，$n$代表买瓜子的资金，$m$ 代表超市瓜子种类数

接下来输入 $m$ 行，每行输入两个正整数$p$和$k$且用一个空格隔开，$p$代表每袋瓜子的价格，$k$代表每袋瓜子的重量

输出

输出一个正整数，代表 $n$ 元钱最多能采购到的瓜子重量(千克)

80 2
18 10
30 20

50

提示

$1<=n<=1000$

$1<=m<=30$

$1<p<101$

$1<k<101$