题目背景

花になって

且作芳华

ほらニヒルに笑って

看啊声声冷笑

その顔にぞくぞくして目が離せない

面目可憎却难以偏移视线

味見して

一品个中滋味

君の毒は私の薬って包んであげるから笑って

我之良方包覆君之剧毒还请一笑

题目描述

猫猫是一位极具天赋的药师，目前在后宫的翡翠宫为今上的宠妃玉叶妃下做试毒侍女。

后宫中有 $N$ 株草药，对于第 $i$ 株草药，猫猫需要花费 $t_i$ 的时间采集它，并获得 $v_i$ 的药材。猫猫不能采草药超过 $T$ 秒，不然会被玉叶妃的随身侍女红娘骂的……

请问在有限的时间内，猫猫最多可以采集到最多多少价值的药草？

输入格式

第一行为两个整数 $T(1\leq T \leq 1000)$ 和 $N(1\leq M \leq 100)$。代表时间和草药数。

接下来一共 $N$ 行，每行两个整数 $t_i,v_i$，代表采集这株草药的时间与价值。

输出格式

仅一行，即在规定时间内可采集的草药价值的最大值。

样例

70 3
71 100
69 1
1 2

3

数据范围

对于 $100$ 的数据， 保证 $1\leq T \leq 1000,1\leq N \leq 100$。