/
実行時間制限: 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).
- 入力される値はすべて整数である.
小課題
- (15 点) M \leqq 500,N = 1.
- (15 点) M \leqq 500,A_{1} - B_{1} = A_{2} - B_{2} = \cdots = A_{N} - B_{N}.
- (30 点) M \leqq 500.
- (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 の制約を満たす.