分数: 400 分
问题陈述
高桥是一名送货员。今天,他收到了 N 交付请求。
如果他接受 i第一个请求 (1 \leq i \leq N),他获得奖励 P_i 日元,但产生的费用为 C_i 日元燃料和其他费用。因此,接受该项目的净利润 i第一个请求是 P_i - C_i 日元(净利润可以为负)。此外,包裹的重量 i第一个请求是 W_i。如果他不接受请求,则该请求不会产生奖励或费用,也无需携带包裹。
高桥会选择接受 0 或更多请求 N 请求。每个请求要么被接受,要么不被接受;同一请求不能被多次接受。如果没有选择请求,则总重量和总净利润均为 0.
但是,所选请求中的所有包裹都必须装载到卡车上并在一次行程中交付。由于卡车的最大载重量为 S,所选请求的包裹总重量不得超过 S.
此外,为了支付本月的租金,所选请求的净利润总额必须至少为 T.
总结一下,让 A (A \subseteq \{1, 2, \ldots, N\}) 是所选请求的集合。我们想要找到一个选择 A 满足以下两个条件:
- 所选请求的包裹总重量最多为 S。也就是说, \displaystyle\sum_{i \in A} W_i \leq S
- 所选请求的总净利润至少为 T。也就是说, \displaystyle\sum_{i \in A} (P_i - C_i) \geq T
判断是否有这样的集合 A 存在。如果存在,则输出最小值
所有集合中的 |A| 所有集合中 A 满足条件。如果不存在则输出 -1.
约束
- 1 \leq N \leq 50
- 1 \leq S \leq 10^4
- 1 \leq T \leq 10^4
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
- 所有输入均为整数
输入
N S T P_1 C_1 W_1 P_2 C_2 W_2 \vdots P_N C_N W_N
第一行包含请求数 N, 最大卡车容量 S,以及最低要求的净利润总额 T,用空格分隔。
如下 N 行, i第行 (1 \leq i \leq N) 包含奖励 P_i,费用 C_i,以及包裹重量 W_i 为 i-第一个请求,以空格分隔。
输出
如果存在满足条件的请求选择,则在单行上输出所选请求的最小数量。如果不存在这样的选择,则输出 -1 在一行上。
示例输入 1
4 8 10 8 3 3 7 4 4 12 4 5 3 5 2
示例输出 1
2
示例输入 2
5 10 20 8 3 5 6 4 6 9 5 7 5 2 4 7 6 3
示例输出 2
-1
示例输入 3
10 30 50 60 5 25 30 2 12 25 3 11 20 5 10 18 4 9 15 6 8 12 3 7 10 4 6 8 5 5 5 3 4
示例输出 3
1