#P5940. [Usaco2022 Dec]Bribing Friends G
[Usaco2022 Dec]Bribing Friends G
题目描述
Bessie 想去看纪录片《Bovine Genomics》,但她的朋友们需要一些报酬才愿意陪她。Bessie 有 枚牛币和 个冰淇淋甜筒,共有 个朋友。第 个朋友的人气值为 ,通常需要支付 枚牛币才能请到。每交给该朋友 个甜筒,就可以少付 枚牛币。可以使用多次整数折扣,但最多只能把该朋友的牛币费用减到 。
在牛币和甜筒的预算内,求所有受邀朋友的人气值之和的最大值。
输入格式
第一行三个整数 ,满足 、。
接下来 行,每行三个整数 ,各自均在 到 之间。
输出格式
输出一个整数,表示能获得的最大人气值之和。
样例 #1
样例输入 #1
3 10 8
5 5 4
6 7 3
10 6 3
样例输出 #1
15
样例解释 #1
可以选择朋友 和 。给朋友 四枚牛币和四个甜筒,给朋友 六枚牛币和三个甜筒(朋友 无需折扣,额外的甜筒并非必要),总人气值为 。
测试点性质
- 测试点 2–4 满足 且所有 。
- 测试点 5–7 满足 。
- 测试点 8–10 满足 。
- 测试点 11–15 满足 。
- 测试点 16–20 无额外限制。