P7029: 贿赂朋友
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Bessie 想要观看纪录片：奶牛基因组学，但她不想一个人去。不幸的是，她的朋友们没有足够的热情和她一起去！于是，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂武器库中有两种工具：哞尼和冰激凌甜筒。
Bessie
有 N（1≤N≤2000
）个朋友。然而，并非所有的朋友都是生而平等的！朋友 i
有受欢迎度 Pi（1≤Pi≤2000
），Bessie
想最大化陪她的朋友们的受欢迎度之和。朋友 i 只有当 Bessie 给了她 Ci（1≤Ci≤2000
）哞尼才愿意陪她。如果 Bessie
给她 Xi（1≤Xi≤2000
）个冰激凌甜筒，她还可以给 Bessie 1
哞尼的折扣。Bessie 可以从朋友那里得到任意整数数量的折扣，只要这些折扣不会使得朋友倒给她哞尼。
Bessie
有 A 哞尼和 B 个冰激凌甜筒可供使用（0≤A,B≤2000）。请帮助她求出如果她以最优方案花费她的哞尼和冰激凌甜筒，她可以达到的最大受欢迎度之和。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第 1
行包含三个整数 N，A
和 B，分别表示 Bessie
拥有的朋友的数量，哞尼的数量和冰激凌甜筒的数量。
以下 N
行每行包含三个整数 Pi，Ci
和 Xi，表示受欢迎度（Pi
），贿赂朋友 i
陪 Bessie 所需要的哞尼（Ci），以及从朋友 i
处获得 1
哞尼的折扣所需要的冰激凌甜筒的数量（Xi）。
【
输出格式】
（输出至终端 /
标准输出）：
输出陪 Bessie
的朋友们的最大受欢迎度之和，假设她以最优方案花费她的哞尼和冰激凌甜筒。
【
输入样例】
：
3 10 8
5 5 4
6 7 3
10 6 3
【
输出样例】
：
15
【样例说明】
Bessie
可以将 4 哞尼和 4 个冰激凌甜筒给奶牛 1，将 6
哞尼和 3 个冰激凌甜筒给奶牛 3，这样奶牛 1
和 3 就可以陪她，得到 5+10=15 的受欢迎度。
【
测试点性质】
：
测试点 2-4
满足 N≤5 以及 Ci=1。
测试点 5-7
满足 B=0。
测试点 8-10
满足 N,A,B,Pi,Ci,Xi≤50。
测试点 11-15
满足 N,A,B,Pi,Ci,Xi≤200。
测试点 16-20
没有额外限制。