08761. 社团嘉年华集章 · 林老师的题库

题目描述

学校举办社团嘉年华，操场上共有 $n$ 个社团摊位，每个摊位都设置了一个体验项目。体验第 $i$ 个项目需要 $a_{i}$ 分钟（含排队时间），完成后可以领取 $b_{i}$ 枚社团印章。每个项目最多体验一次，印章可以累计。

你总共只有 $T$ 分钟参加嘉年华，想让领到的印章总数尽可能多。请计算在总体验时间不超过 $T$ 分钟的前提下，最多能领到多少枚印章。

第一行两个整数 $T$ 和 $n$ ，表示总时长（分钟）与摊位（项目）个数。

接下来 $n$ 行，第 $i$ 行两个整数 $a_{i}$ 和 $b_{i}$ ，表示第 $i$ 个项目需要的分钟数与能领到的印章数。

一行一个整数，表示最多能领到的印章总数。

输入

输出

样例解释：体验第 $1$ 、 $3$ 个项目，共花 $30 + 20 = 50$ 分钟，恰好用完时间，领到 $12 + 9 = 21$ 枚印章；没有总时间不超过 $50$ 分钟且印章更多的方案。

样例解释：唯一的项目需要 $10$ 分钟，超过总时长 $8$ 分钟，一个项目也体验不了，只能领到 $0$ 枚印章。

对于 $100%$ 的数据： $0 \leq T \leq 1 0^{4}$ ， $1 \leq n \leq 100$ ， $1 \leq a_{i} \leq 300$ ， $1 \leq b_{i} \leq 30$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。