F - チョコレートを増やせ (Increase Chocolates) 解説 /

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

配点 : 100 点

問題文

オランダではチョコレートが有名である.オランダのとあるチョコレート店では現在キャンペーンを行っており,チョコレートとの交換に使えるチケットが,チョコレート 1 つにつき 1 枚付けられている.

チケットは N 種類の交換規則によってチョコレートと交換することができる.i 番目 (1 \leqq i \leqq N) の交換規則を使うと,店員に A_{i} 枚のチケットを渡したとき,B_{i} 個のチョコレートを受け取ることができる.ここで,A_{i} > B_{i} が成り立つ.交換規則は好きな順で何回でも使うことができ,交換で受け取るチョコレートにもチケットが付いている.

あなたは,交換規則を駆使して,できるだけ少ない個数のチョコレートを購入して,EGOI の参加者に 1 個ずつチョコレートを配りたいと考えている.ただし,あなたははじめチョコレートもチケットも持っておらず,購入と交換以外の方法でチョコレートやチケットを受け取ることはできない.また,参加者に配るチョコレートにチケットが付いている必要はない.

EGOI の参加者は M 人いるが,何人かはチョコレートが苦手かもしれない.そこで,各 k = 1, 2, \ldots, M について,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値が知りたい.

交換規則と EGOI の参加人数 M の情報が与えられたとき,各 k = 1, 2, \ldots, M について,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値を求めるプログラムを作成せよ.

入力

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

N M
A_{1} B_{1}
A_{2} B_{2}
\vdots
A_{N} B_{N}

出力

標準出力に M 行で出力せよ.k 行目 (1 \leqq k \leqq M) には,k 個以上のチョコレートを用意するために購入する必要があるチョコレートの個数の最小値を出力せよ.

制約

  • 1 \leqq N \leqq 500.
  • 1 \leqq M \leqq 100\,000.
  • 1 \leqq B_{i} < A_{i} < M (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (15 点) M \leqq 500,N = 1.
  2. (15 点) M \leqq 500,A_{1} - B_{1} = A_{2} - B_{2} = \cdots = A_{N} - B_{N}.
  3. (30 点) M \leqq 500.
  4. (40 点) 追加の制約はない.

入力例 1

2 12
3 1
5 2

出力例 1

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

例えば,6 個のチョコレートを購入し,以下のように交換規則を使うことで,9 個のチョコレートを用意することができる.

  • はじめ,チョコレートが 6 個,チケットが 6 枚ある.
  • 2 番目の交換規則を使う.チケット 5 枚を渡し,チョコレート 2 個とチケット 2 枚を受け取る.チョコレートが 8 個,チケットが 3 枚になる.
  • 1 番目の交換規則を使う.チケット 3 枚を渡し,チョコレート 1 個とチケット 1 枚を受け取る.チョコレートが 9 個,チケットが 1 枚になる.

購入するチョコレートの数が 5 個以下のとき,最終的なチョコレートの数を 9 個以上にすることはできないため,9 行目には 6 を出力する.

この入力例は小課題 3, 4 の制約を満たす.

入力例 2

1 10
4 3

出力例 2

1
2
3
4
4
4
4
5
5
5

この入力例はすべての小課題の制約を満たす.

入力例 3

3 10
3 1
5 3
4 2

出力例 3

1
2
3
3
4
4
5
5
5
6

この入力例は小課題 2, 3, 4 の制約を満たす.


出典

JOIG 2023/2024 春季トレーニング Contest Day2