题目背景

第十二届蓝桥杯青少年组国赛2021年5月C++组第4题

题目描述

某校庆祝元旦需要采购一些瓜子在联欢会上食用，学校给了固定资金 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 元钱最多能采购到的瓜子重量（千克）。

样例 #1

样例输入 #1

80 2
18 10
30 20

样例输出 #1

50