#P5940. [Usaco2022 Dec]Bribing Friends G

    ID: 4940 传统题 1000ms 256MiB 尝试: 9 已通过: 2 难度: 6 上传者: 标签>难度分类提高贪心交换论证动态规划0/1 背包前后缀状态分解枚举与搜索枚举中间点暴力枚举倒序更新避免重复使用CF2100

[Usaco2022 Dec]Bribing Friends G

题目描述

Bessie 想去看纪录片《Bovine Genomics》,但她的朋友们需要一些报酬才愿意陪她。Bessie 有 AA 枚牛币和 BB 个冰淇淋甜筒,共有 NN 个朋友。第 ii 个朋友的人气值为 PiP_i,通常需要支付 CiC_i 枚牛币才能请到。每交给该朋友 XiX_i 个甜筒,就可以少付 11 枚牛币。可以使用多次整数折扣,但最多只能把该朋友的牛币费用减到 00。

在牛币和甜筒的预算内,求所有受邀朋友的人气值之和的最大值。

输入格式

第一行三个整数 N,A,BN,A,B,满足 1≤N≤20001\le N\le2000、0≤A,B≤20000\le A,B\le2000。

接下来 NN 行,每行三个整数 Pi,Ci,XiP_i,C_i,X_i,各自均在 11 到 20002000 之间。

输出格式

输出一个整数,表示能获得的最大人气值之和。

样例 #1

样例输入 #1

3 10 8
5 5 4
6 7 3
10 6 3

样例输出 #1

15

样例解释 #1

可以选择朋友 11 和 33。给朋友 11 四枚牛币和四个甜筒,给朋友 33 六枚牛币和三个甜筒(朋友 33 无需折扣,额外的甜筒并非必要),总人气值为 5+10=155+10=15。

测试点性质

  • 测试点 2–4 满足 N≤5N\le5 且所有 Ci=1C_i=1。
  • 测试点 5–7 满足 B=0B=0。
  • 测试点 8–10 满足 N,A,B,Pi,Ci,Xi≤50N,A,B,P_i,C_i,X_i\le50。
  • 测试点 11–15 满足 N,A,B,Pi,Ci,Xi≤200N,A,B,P_i,C_i,X_i\le200。
  • 测试点 16–20 无额外限制。