题目描述

每株草药有采摘时间和价值，每株只能采摘一次。在给定的时间 $T$ 内，求最多能采到的草药总价值。

输入格式

第一行 $T,N$。随后 $N$ 行，每行采摘一株草药所需的时间和价值。

输出格式

输出最大总价值。

样例

70 3
71 100
69 1
1 2

3

数据范围

对于30%的数据，$N\le10$；对于100%的数据，$1\le N\le100$，$1\le T\le1000$，每株草药的时间和价值都在1至100之间。