E - プレイリストのジャンル偏り最小化 解説 /

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

配点 : 433 点

問題文

高橋君は 2N 曲の候補曲からプレイリストを作ろうとしています。

i 番目の曲 (1 \leq i \leq 2N) はジャンル B_i に属しており、再生時間は A_i 秒です。

高橋君は候補曲の中から 1 曲以上を選び（各曲は最大 1 回まで選べます）、好きな順番に並べてプレイリストを作ります。

ただし、選んだ曲の再生時間の合計は K 秒以上でなければなりません。

作ったプレイリストにおいて、同じジャンルの曲が連続して並んでいる区間に含まれる曲数の最大値を「偏りスコア」と呼びます。

より正確には、プレイリスト中の連続する曲の並びであって、それらがすべて同一ジャンルに属するようなものを考え、その曲数の最大値が偏りスコアです。

条件を満たす曲の選び方と並べ方すべての中で、偏りスコアの最小値を求めてください。

すべての曲を選んでも再生時間の合計が K 秒未満となり、条件を満たせない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 150
  • 1 \leq K \leq 10^9
  • 1 \leq B_i \leq 2N
  • 1 \leq A_i \leq 10^6
  • 入力はすべて整数である

入力

N K
B_1 A_1
B_2 A_2
\vdots
B_{2N} A_{2N}
  • 1 行目には、候補曲数の半分を表す整数 N と、必要な再生時間の合計の下限を表す整数 K がスペース区切りで与えられる。
  • 続く 2N 行のうち i 行目 (1 \leq i \leq 2N) には、i 番目の曲のジャンル B_i と再生時間 A_i がスペース区切りで与えられる。

出力

偏りスコアの最小値を 1 行で出力してください。条件を満たすように曲を選べない場合は -1 を出力してください。

入力例 1

3 15
1 6
1 5
2 4
2 7
3 3
3 8

出力例 1

1

入力例 2

2 31
1 8
2 7
2 6
3 9

出力例 2

-1

入力例 3

8 120
1 15
1 12
2 20
2 7
3 9
3 18
4 25
5 5
5 14
6 11
7 30
7 6
8 10
9 16
10 8
10 13

出力例 3

1

入力例 4

20 650
1 45
1 32
1 28
2 60
2 15
3 22
3 48
4 35
4 40
5 10
5 55
6 70
6 18
7 25
7 27
8 80
9 12
9 44
10 33
10 36
11 90
12 14
12 29
13 50
13 52
14 20
15 65
15 17
16 31
16 39
17 75
18 11
18 24
19 46
20 58
21 13
22 41
23 30
24 62
25 19

出力例 4

1

入力例 5

1 2
1 1
1 1

出力例 5

2

Score : 433 pts

Problem Statement

Takahashi is trying to create a playlist from 2N candidate songs.

The i-th song (1 \leq i \leq 2N) belongs to genre B_i and has a duration of A_i seconds.

Takahashi selects one or more songs from the candidates (each song can be selected at most once) and arranges them in any order he likes to create a playlist.

However, the total duration of the selected songs must be at least K seconds.

In the created playlist, the maximum number of songs contained in a consecutive segment where all songs belong to the same genre is called the "bias score."

More precisely, consider all consecutive subsequences of songs in the playlist such that all songs in each subsequence belong to the same genre; the bias score is the maximum number of songs among all such subsequences.

Among all possible ways to select and arrange songs that satisfy the conditions, find the minimum possible bias score.

If the total duration is less than K seconds even when all songs are selected, and thus the condition cannot be satisfied, output -1.

Constraints

  • 1 \leq N \leq 150
  • 1 \leq K \leq 10^9
  • 1 \leq B_i \leq 2N
  • 1 \leq A_i \leq 10^6
  • All input values are integers

Input

N K
B_1 A_1
B_2 A_2
\vdots
B_{2N} A_{2N}
  • The first line contains an integer N representing half the number of candidate songs, and an integer K representing the lower bound on the total duration, separated by a space.
  • In the following 2N lines, the i-th line (1 \leq i \leq 2N) contains the genre B_i and the duration A_i of the i-th song, separated by a space.

Output

Output the minimum possible bias score in one line. If it is impossible to select songs satisfying the condition, output -1.

Sample Input 1

3 15
1 6
1 5
2 4
2 7
3 3
3 8

Sample Output 1

1

Sample Input 2

2 31
1 8
2 7
2 6
3 9

Sample Output 2

-1

Sample Input 3

8 120
1 15
1 12
2 20
2 7
3 9
3 18
4 25
5 5
5 14
6 11
7 30
7 6
8 10
9 16
10 8
10 13

Sample Output 3

1

Sample Input 4

20 650
1 45
1 32
1 28
2 60
2 15
3 22
3 48
4 35
4 40
5 10
5 55
6 70
6 18
7 25
7 27
8 80
9 12
9 44
10 33
10 36
11 90
12 14
12 29
13 50
13 52
14 20
15 65
15 17
16 31
16 39
17 75
18 11
18 24
19 46
20 58
21 13
22 41
23 30
24 62
25 19

Sample Output 4

1

Sample Input 5

1 2
1 1
1 1

Sample Output 5

2