E - Choosing Treasure Chests Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は冒険者です。ダンジョンを探索した結果、N 個の宝箱を発見しました。

i 番目の宝箱の重さは A_i キログラムで、価値は B_i です。

高橋君が持っているリュックサックには、重さの合計が M キログラム以下となるように宝箱を入れることができます。高橋君は N 個の宝箱の中から何個か（0個でもよい）を選んでリュックサックに入れて持ち帰ろうとしています。ただし、各宝箱は1個ずつしか存在しないため、同じ宝箱を複数回選ぶことはできません。

高橋君は、選んだ宝箱の重さの合計が M キログラム以下であるという制約のもとで、選んだ宝箱の価値の合計を最大化したいと考えています。価値の合計が最大となるような選び方を最適な選び方と呼ぶことにします。最適な選び方は複数存在する場合があります。

各宝箱 i (1 \leq i \leq N) について、宝箱 i を含むような最適な選び方が存在するかどうかを判定してください。

制約

  • 1 \leq N \leq 1,000
  • 1 \leq M \leq 3,000
  • 1 \leq A_i \leq M (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、宝箱の個数を表す整数 N と、リュックサックの容量を表す整数 M が、スペース区切りで与えられる。
  • i + 1 行目 (1 \leq i \leq N) には、i 番目の宝箱の重さを表す整数 A_i と、価値を表す整数 B_i が、スペース区切りで与えられる。

出力

N 行出力してください。

i 行目には、宝箱 i を含むような最適な選び方が存在する場合は Yes を、存在しない場合は No を出力してください。

入力例 1

3 5
2 3
3 4
3 3

出力例 1

Yes
Yes
No

入力例 2

4 4
2 5
2 5
2 5
3 1

出力例 2

Yes
Yes
Yes
No

入力例 3

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

出力例 3

Yes
Yes
Yes
No
Yes
No

入力例 4

10 15
3 10
4 12
5 14
2 7
1 3
6 18
7 20
8 22
3 9
4 11

出力例 4

Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No

入力例 5

1 1
1 1

出力例 5

Yes

Score : 466 pts

Problem Statement

Takahashi is an adventurer. After exploring a dungeon, he discovered N treasure chests.

The i-th treasure chest has a weight of A_i kilograms and a value of B_i.

Takahashi's backpack can hold treasure chests as long as their total weight is at most M kilograms. Takahashi plans to select some number of treasure chests (possibly zero) from the N chests to put in his backpack and carry home. However, since each treasure chest exists only once, the same chest cannot be selected multiple times.

Takahashi wants to maximize the total value of the selected treasure chests, subject to the constraint that the total weight of the selected chests is at most M kilograms. A selection that maximizes the total value is called an optimal selection. There may be multiple optimal selections.

For each treasure chest i (1 \leq i \leq N), determine whether there exists an optimal selection that includes treasure chest i.

Constraints

  • 1 \leq N \leq 1,000
  • 1 \leq M \leq 3,000
  • 1 \leq A_i \leq M (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of treasure chests and an integer M representing the capacity of the backpack, separated by a space.
  • The (i + 1)-th line (1 \leq i \leq N) contains an integer A_i representing the weight of the i-th treasure chest and an integer B_i representing its value, separated by a space.

Output

Print N lines.

On the i-th line, print Yes if there exists an optimal selection that includes treasure chest i, and No otherwise.

Sample Input 1

3 5
2 3
3 4
3 3

Sample Output 1

Yes
Yes
No

Sample Input 2

4 4
2 5
2 5
2 5
3 1

Sample Output 2

Yes
Yes
Yes
No

Sample Input 3

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

Sample Output 3

Yes
Yes
Yes
No
Yes
No

Sample Input 4

10 15
3 10
4 12
5 14
2 7
1 3
6 18
7 20
8 22
3 9
4 11

Sample Output 4

Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No

Sample Input 5

1 1
1 1

Sample Output 5

Yes