题目描述

山洞中有 $m$ 株不同的草药。采摘第 $i$ 株草药需要 $t_i$ 分钟，可以获得 $v_i$ 点价值。每株草药最多采摘一次。

霸王龙一共有 $T$ 分钟，请计算在规定时间内能够获得的最大总价值。

输入格式

第一行包含两个整数 $T,m$，表示总时间和草药数量。

接下来 $m$ 行，每行输入两个整数 $t_i,v_i$。

输出格式

输出能够获得的最大总价值。

70 3
71 100
69 1
1 2

3

数据范围与提示

• $1\le T\le 1000$
• $1\le m\le 100$
• $1\le t_i,v_i\le 100$