← 返回题目列表

AtCoder · awc0023_d

D. 包裹递送

中文机器翻译题面 查看原题

分数: 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