E - 山頂コレクション 解説 /

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

配点 : 433 点

問題文

高橋君は、縦走ルート沿いに一列に並ぶ N 個の山の山頂を巡ろうとしています。山頂にはルートの入口側から順に 1, 2, \ldots, N の番号がついており、高橋君はルートの入口から出発して番号の小さい方から大きい方へ一方通行で進みます。一度通り過ぎた山頂に戻ることはできません。

各山頂 i には「入山料」 C_i 円と「標高」 S_i が設定されています。高橋君はルート上を進みながら、各山頂に差し掛かったとき、その山頂に登頂するか、登頂せずに通過するかを選ぶことができます。登頂せずに通過する場合、入山料はかかりません。登頂する場合はその山頂の入山料を支払う必要があります。

高橋君には登山のこだわりがあり、次の条件をすべて満たすように登頂する山頂を選びたいと考えています。

  • 登頂数の上限： 登頂する山頂の数は K 個以下でなければならない。
  • 標高の単調増加： 登頂する山頂を番号の昇順に並べたとき、それらの標高は狭義単調増加でなければならない。すなわち、山頂 i_1 < i_2 < \cdots < i_m に順に登頂するとき、 S_{i_1} < S_{i_2} < \cdots < S_{i_m} を満たす必要がある。
  • 予算の制限： 登頂する山頂の入山料の合計が所持金 B 円以下でなければならない。すなわち、 C_{i_1} + C_{i_2} + \cdots + C_{i_m} \leq B を満たす必要がある。

高橋君は、上記の条件をすべて満たしつつ、登頂する山頂の数 m を最大化したいです。最大の m を求めてください。なお、一つも登頂しない（ m = 0 ）ことも許されます。

制約

  • 1 \leq N \leq 500
  • 1 \leq K \leq 50
  • 1 \leq B \leq 500
  • 1 \leq C_i \leq B （ 1 \leq i \leq N ）
  • 1 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
  • S_i \neq S_j （ i \neq j ）
  • 入力はすべて整数である。

入力

N K B
C_1 S_1
C_2 S_2
\vdots
C_N S_N
  • 1 行目には、山頂の数 N 、登頂数の上限 K 、所持金 B がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（ 1 \leq i \leq N ）には、山頂 i の入山料 C_i と標高 S_i がスペース区切りで与えられる。

出力

条件をすべて満たすように山頂を選んだとき、登頂できる山頂の数の最大値 m を 1 行で出力せよ。

入力例 1

5 3 10
3 100
2 200
5 150
4 300
1 400

出力例 1

3

入力例 2

4 3 3
2 100
2 200
2 300
2 400

出力例 2

1

入力例 3

10 5 20
3 500
2 100
5 300
1 200
4 800
2 600
3 150
6 900
1 700
5 1000

出力例 3

5

入力例 4

20 10 50
5 320
3 150
7 410
2 80
4 500
6 230
1 600
8 90
3 700
5 350
2 850
4 120
6 950
1 40
3 1100
7 560
2 1200
5 780
4 1350
3 999

出力例 4

10

入力例 5

1 1 1
1 1000000000

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is trying to visit the summits of N mountains lined up in a row along a traverse route. The summits are numbered 1, 2, \ldots, N from the entrance side of the route, and Takahashi starts from the entrance and proceeds one-way from lower-numbered to higher-numbered summits. He cannot return to a summit he has already passed.

Each summit i has an "entrance fee" of C_i yen and an "elevation" of S_i. As Takahashi proceeds along the route, when he reaches each summit, he can choose either to climb it or to pass through without climbing. If he passes through without climbing, no entrance fee is charged. If he climbs it, he must pay that summit's entrance fee.

Takahashi has particular preferences for his mountaineering and wants to select which summits to climb such that all of the following conditions are satisfied:

  • Upper limit on number of climbs: The number of summits climbed must be at most K.
  • Strictly increasing elevation: When the climbed summits are listed in ascending order of their numbers, their elevations must be strictly increasing. That is, if he climbs summits i_1 < i_2 < \cdots < i_m in order, then S_{i_1} < S_{i_2} < \cdots < S_{i_m} must hold.
  • Budget constraint: The total entrance fees of the climbed summits must not exceed his funds of B yen. That is, C_{i_1} + C_{i_2} + \cdots + C_{i_m} \leq B must hold.

Takahashi wants to maximize the number of summits climbed m while satisfying all the above conditions. Find the maximum value of m. Note that climbing no summits (m = 0) is also allowed.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq K \leq 50
  • 1 \leq B \leq 500
  • 1 \leq C_i \leq B (1 \leq i \leq N)
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • S_i \neq S_j (i \neq j)
  • All inputs are integers.

Input

N K B
C_1 S_1
C_2 S_2
\vdots
C_N S_N
  • The first line contains the number of summits N, the upper limit on climbs K, and the available funds B, separated by spaces.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the entrance fee C_i and elevation S_i of summit i, separated by spaces.

Output

Print in one line the maximum number of summits m that can be climbed while satisfying all the conditions.

Sample Input 1

5 3 10
3 100
2 200
5 150
4 300
1 400

Sample Output 1

3

Sample Input 2

4 3 3
2 100
2 200
2 300
2 400

Sample Output 2

1

Sample Input 3

10 5 20
3 500
2 100
5 300
1 200
4 800
2 600
3 150
6 900
1 700
5 1000

Sample Output 3

5

Sample Input 4

20 10 50
5 320
3 150
7 410
2 80
4 500
6 230
1 600
8 90
3 700
5 350
2 850
4 120
6 950
1 40
3 1100
7 560
2 1200
5 780
4 1350
3 999

Sample Output 4

10

Sample Input 5

1 1 1
1 1000000000

Sample Output 5

1