2700 问题 H: 蓝桥杯2022年第十三届决赛真题-搬砖

时间限制: 1s 内存限制: 256MB 提交: 1306 解决: 320
题目描述

这天,小明在搬砖。

他一共有 n 块砖,他发现第 i 砖的重量为 wi,价值为 vi。他突然想从这些砖中选一些出来从下到上堆成一座塔,并且对于塔中的每一块砖来说,它上面所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值(即塔中所有砖块的价值和)最大是多少。

输入

输入共 n + 1 行,第一行为一个正整数 n,表示砖块的数量。

后面 n 行,每行两个正整数 wi , vi 分别表示每块砖的重量和价值。

输出
一行,一个整数表示答案。 
样例输入
5
4 4
1 1
5 2
5 5
4 3
样例输出
10
提示

选择第 1、2、4 块砖,从上到下按照 2、1、4 的顺序堆成一座塔,总价值为 4 + 1 + 5 = 10 。

对于 20% 的数据,保证 n ≤ 10;

对于 100% 的数据,保证 n ≤ 1000; wi ≤ 20; vi ≤ 20000 。

比赛公告


请对本次比赛进行一些描述,公告内容应当包含:
比赛的创办者或组织;
本次比赛的目的或意义;
本次比赛的考点、语言或类型;或其他注意事项及描述等。
至少保证30个汉字长度。