题目描述

山洞里有M株草药，每株草药都有采摘时间和价值，每株最多采摘一次。辰辰共有T个单位时间，请帮助他选择草药，使总采摘时间不超过T，且总价值最大。

输入格式

第一行两个整数T、M。接下来M行，每行两个整数，分别表示一株草药的采摘时间和价值。

输出格式

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

样例

70 3
71 100
69 1
1 2

3

数据范围

1≤T≤1000，1≤M≤100；采摘时间和价值均在1至100之间。