Description

ZHB已经是一个老年人了，他经常需要一些中药补补身体，但无奈于空空的钱包，他只能自己到燕山上去采药。

碰巧的是，他找到了一个山洞，山洞里全部都是草药。ZHB很想把它们全部采走，但受制于自己身体，他只能在有限的时间内去采。

已知每一株药草都有对应的药效和采摘时间，请你设计一个算法帮助ZHB，让TA在有限的时间内采摘的药草药效总和最大。

Input Format

输入第一行有两个整数T（1 <= T <= 100000）和M（1 <= M <= 10000），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到10000之间（包括1和10000）的整数，分别表示采摘某种草药的时间和这种草药的药效。

Output Format

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

70 3
71 100
69 1
1 2​

140​

Hint

本题基于1390改编，有些许不同，请注意

Source

动态规划