D - 荷物の配達 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は配達員として働いています。今日は N 個の配達依頼が届いています。

i 番目 (1 \leq i \leq N) の依頼を受けると、報酬として P_i 円を受け取れますが、燃料代などの経費として C_i 円がかかります。したがって、i 番目の依頼を受けた場合の純利益は P_i - C_i 円です（純利益は負になることもあります）。また、i 番目の依頼の荷物の重量は W_i です。依頼を受けなければ、その依頼に関する報酬・経費は発生せず、荷物を運ぶ必要もありません。

高橋君は N 個の依頼の中から 0 個以上の依頼を選んで受けることにします。各依頼は受けるか受けないかのどちらかであり、同じ依頼を複数回受けることはできません。依頼を 1 つも選ばない場合、重量の合計・純利益の合計はともに 0 となります。

ただし、選んだ依頼の荷物はすべてトラックに積んで 1 回の配達で運ぶ必要があります。トラックの積載量の上限は S であるため、選んだ依頼の荷物の重量の合計が S 以下でなければなりません。

さらに、高橋君は今月の家賃を支払うために、選んだ依頼の純利益の合計が T 以上である必要があります。

以上をまとめると、選んだ依頼の集合を A（A \subseteq \{1, 2, \ldots, N\}）として、次の 2 つの条件をともに満たす 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

1 行目には、依頼の個数 N、トラックの積載量の上限 S、必要な純利益の合計の下限 T が、スペース区切りで与えられる。

続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の依頼の報酬 P_i、経費 C_i、荷物の重量 W_i が、スペース区切りで与えられる。

出力

条件を満たす依頼の選び方が存在する場合は、選んだ依頼の個数の最小値を 1 行で出力してください。存在しない場合は -1 を 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

Score : 400 pts

Problem Statement

Takahashi works as a delivery person. Today, he has received N delivery requests.

If he accepts the i-th request (1 \leq i \leq N), he receives a reward of P_i yen, but incurs expenses of C_i yen for fuel and other costs. Therefore, the net profit from accepting the i-th request is P_i - C_i yen (the net profit can be negative). Additionally, the weight of the package for the i-th request is W_i. If he does not accept a request, no reward or expense is incurred for that request, and there is no need to carry the package.

Takahashi will choose to accept 0 or more requests from the N requests. Each request is either accepted or not accepted; the same request cannot be accepted multiple times. If no requests are selected, both the total weight and the total net profit are 0.

However, all packages from the selected requests must be loaded onto a truck and delivered in a single trip. Since the truck has a maximum capacity of S, the total weight of the packages from the selected requests must be at most S.

Furthermore, in order to pay this month's rent, the total net profit from the selected requests must be at least T.

To summarize, let A (A \subseteq \{1, 2, \ldots, N\}) be the set of selected requests. We want to find a selection of A that satisfies both of the following conditions:

  • The total weight of the packages from the selected requests is at most S. That is, \displaystyle\sum_{i \in A} W_i \leq S
  • The total net profit from the selected requests is at least T. That is, \displaystyle\sum_{i \in A} (P_i - C_i) \geq T

Determine whether such a set A exists. If it exists, output the minimum value of |A| among all sets A satisfying the conditions. If it does not exist, output -1.

Constraints

  • 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)
  • All inputs are integers

Input

N S T
P_1 C_1 W_1
P_2 C_2 W_2
\vdots
P_N C_N W_N

The first line contains the number of requests N, the maximum truck capacity S, and the minimum required total net profit T, separated by spaces.

In the following N lines, the i-th line (1 \leq i \leq N) contains the reward P_i, the expense C_i, and the package weight W_i for the i-th request, separated by spaces.

Output

If a selection of requests satisfying the conditions exists, output the minimum number of selected requests on a single line. If no such selection exists, output -1 on a single line.

Sample Input 1

4 8 10
8 3 3
7 4 4
12 4 5
3 5 2

Sample Output 1

2

Sample Input 2

5 10 20
8 3 5
6 4 6
9 5 7
5 2 4
7 6 3

Sample Output 2

-1

Sample Input 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

Sample Output 3

1