E - Maximum Glutton Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

高橋君はすぬけ君のために N 個の料理を作りました。 料理には 1 から N までの番号がつけられていて、料理 i の甘さは A_i、しょっぱさは B_i です。

高橋君はこれらの料理を好きな順番で並べることができます。 すぬけ君は料理を並べられた順に食べていきますが、ある時点においてそれまでに食べた料理の甘さの合計が X を超えるかしょっぱさの合計が Y を超えた場合、それ以降の料理は食べません。

高橋君は、すぬけ君にできるだけ多くの料理を食べてほしいと思っています。 高橋君がうまく料理を並べたとき、すぬけ君が最大で何個の料理を食べることになるか求めてください。

制約

  • 1\leq N \leq 80
  • 1\leq A_i,B_i \leq 10000
  • 1\leq X,Y \leq 10000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを整数として出力せよ。

入力例 1

4 8 4
1 5
3 2
4 1
5 3

出力例 1

3

高橋君が料理を 2,3,1,4 の順番で並べた場合のすぬけ君の行動を考えます。

  • まず料理 2 を食べる。ここまでに食べた料理の甘さの合計は 3、しょっぱさの合計は 2 である。
  • 次に料理 3 を食べる。ここまでに食べた料理の甘さの合計は 7、しょっぱさの合計は 3 である。
  • 次に料理 1 を食べる。ここまでに食べた料理の甘さの合計は 8、しょっぱさの合計は 8 である。
  • しょっぱさの合計が Y=4 を超えたので、これ以降の料理は食べない。

よって、この並び方の場合すぬけ君は 3 個の料理を食べることになります。

高橋君が料理をどのように並べてもすぬけ君が 4 つ全ての料理を食べることはないので、答えは 3 です。

入力例 2

2 1 1
3 2
3 2

出力例 2

1

入力例 3

2 100 100
3 2
3 2

出力例 3

2

入力例 4

6 364 463
230 381
154 200
328 407
339 94
193 10
115 309

出力例 4

3

Score : 475 points

Problem Statement

Takahashi has prepared N dishes for Snuke. The dishes are numbered from 1 to N, and dish i has a sweetness of A_i and a saltiness of B_i.

Takahashi can arrange these dishes in any order he likes. Snuke will eat the dishes in the order they are arranged, but if at any point the total sweetness of the dishes he has eaten so far exceeds X or the total saltiness exceeds Y, he will not eat any further dishes.

Takahashi wants Snuke to eat as many dishes as possible. Find the maximum number of dishes Snuke will eat if Takahashi arranges the dishes optimally.

Constraints

  • 1 \leq N \leq 80
  • 1 \leq A_i, B_i \leq 10000
  • 1 \leq X, Y \leq 10000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer as an integer.

Sample Input 1

4 8 4
1 5
3 2
4 1
5 3

Sample Output 1

3

Consider the scenario where Takahashi arranges the dishes in the order 2, 3, 1, 4.

  • First, Snuke eats dish 2. The total sweetness so far is 3, and the total saltiness is 2.
  • Next, Snuke eats dish 3. The total sweetness so far is 7, and the total saltiness is 3.
  • Next, Snuke eats dish 1. The total sweetness so far is 8, and the total saltiness is 8.
  • The total saltiness has exceeded Y=4, so Snuke will not eat any further dishes.

Thus, in this arrangement, Snuke will eat three dishes.

No matter how Takahashi arranges the dishes, Snuke will not eat all four dishes, so the answer is 3.

Sample Input 2

2 1 1
3 2
3 2

Sample Output 2

1

Sample Input 3

2 100 100
3 2
3 2

Sample Output 3

2

Sample Input 4

6 364 463
230 381
154 200
328 407
339 94
193 10
115 309

Sample Output 4

3