P83055

PRZ

难度 7 级 初三 动态规划入门 状态压缩
讨论 统计 7通过 15提交 46.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥。

桥已经很旧了, 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过。队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少。

输入

第一行两个数: W 表示桥能承受的最大重量和 n 表示队员总数。

接下来 n 行:每行两个数: t 表示该队员过桥所需时间和 w 表示该队员的重量。

输出

输出一个数表示最少的过桥时间。

样例

样例 1
输入
100 3
24 60
10 40
18 50
输出
42

提示

对于 100\% 的数据,100\le W \le400 ,1\le n\le 16,1\le t\le50,10\le w\le100

来源

其它比赛

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交