题目背景

小雨立志成为一名出色的药师。为了考验她，师傅把她带到一座长满草药的药谷里，交给她一项特别的任务。

题目描述

药谷里生长着若干种草药，每采摘一株某种草药都要花费一定的时间，同时这种草药也有对应的价值。师傅给了小雨一段有限的时间，希望她在这段时间里采到总价值尽可能高的草药。

需要注意的是：

$1$. 每种草药的数量都多得采不完，想采多少株都可以。

$2$. 草药种类繁多，而且有的草药采摘时间特别长。

如果你是小雨，你能算出这段时间里能采到的草药的最大总价值吗？

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和药谷里草药的种类数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘一株第 $i$ 种草药所需的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例

70 3
71 100
69 1
1 2

140

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $m \le 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。