题目描述

辰辰是一位天资聪颖的孩子，他想给正在治疗中的妈妈采一些草药回家。在爬过一段陡峭的山路后，他终于来到了山顶开满野花的药田。

辰辰已经通过一本珍贵的典籍，知道了在这 $M$ 个开阔的地带一共可以采到多少种不同的草药，以及每种草药需要花费多少时间、能收获多少价值。

辰辰今天打算用 $T$ 个小时来采药，每种草药最多只能采一次。他想知道，在不超过 $T$ 小时的前提下，能采到的草药的最大总价值是多少。

输入格式

第一行两个整数 $T$ 和 $M$，表示可用总时间与草药种类数。

接下来 $M$ 行，每行两个整数 $t_i$ 和 $v_i$，表示第 $i$ 种草药需要 $t_i$ 小时、价值为 $v_i$。

输出格式

输出一行一个整数，表示不超过 $T$ 小时能采到的最大总价值。

样例

70 3
71 100
69 1
1 2

3

样例解释

第 $1$ 种草药价值很高，但需要 $71$ 小时，超过总时间 $70$，不能采。

可以采第 $2$、$3$ 种：用时 $1 + 69 = 70$，总价值 $1 + 2 = 3$。

数据范围与部分分

提示

• 可行性剪枝：当前已用时间超过 $T$，无论后面如何选择都不可能合法，应立刻回溯。
• 最优性剪枝：预处理 suffix[i] 为第 $i$ 种到第 $M$ 种草药的价值之和（乐观上界，忽略时间限制）。若 val + suffix[i] <= ans，即使后面全部采完也不可能超过当前最优，应回溯。
• 满分亦可用记忆化搜索或 01 背包 DP；本阶梯版重点在搜索剪枝。