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.

题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

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

80 2
18 10
30 20

50