题目描述

山洞里有 $n$ 种不同的草药，每种草药可以无限制采摘。采第 $i$ 种草药需要 $t_i$ 的时间，其价值为 $v_i$。总共可用时间为 $T$。求在时间不超过 $T$ 的情况下，能采到的草药最大总价值。

输入格式

第一行两个整数 $T,n$。 接下来 $n$ 行，每行两个整数 $t_i,v_i$。

输出格式

一个整数，最大总价值。

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

140

数据范围

$1\le T\le 10^6$，$1\le n\le 200$，$1\le t_i,v_i\le 10^4$，答案不超过 $2^{31}-1$。