题目描述

小可正在玩一款闯关游戏！游戏中有 $n$ 种不同类型的宝箱，每种宝箱开启后都能获得一定积分，但开启也需要花费时间。

• 第 $i$ 种宝箱，开启后能获得 $p_i$ 点积分，但需要花费 $t_i$ 秒时间。
• 同一种宝箱可以重复开启多次（数量不限），每次开启都能获得相同的积分，花费相同的时间。
• 游戏总时长为 $m$ 秒。

小可想在时间限制内，通过开启宝箱获得尽可能多的积分。请问她最多能获得多少积分？

输入格式

第一行两个整数 $m$ 和 $n$，分别表示游戏总时长（秒）和宝箱种类数。

接下来 $n$ 行，每行两个整数 $p_i$ 和 $t_i$，表示开启第 $i$ 种宝箱能获得的积分和需要花费的时间。

输出格式

输出一行一个整数，表示小可在 $m$ 秒内最多能获得的积分。

样例

300 4
100 60
250 120
120 100
35 20

605

数据范围

对于 100% 的数据：$1 \le n, m \le 10^4$，$1 \le p_i, t_i \le 10^4$