0169 - れんさんがお仕事したい！

時間制限 2 秒 / メモリ制限 256 MB / 得点 10 / Writer ei1333 / x 1 / 統計 /

    タグ:
TLE
2sec
MLE
256MB
得点
10

問題

情報処理部に所属するれんさんは、毎日情報を処理する仕事をたくさん任されてで大忙し！ それぞれの仕事には、仕事を任される時刻と れんさんが仕事を完遂するまでに必要な所要時間が決まっています。また、仕事にはそれぞれ重要度が設定されていて、れんさんは 各地点で 現在任されている仕事のうち最も重要な仕事を行います。例えば、ある仕事 i をしている途中で その仕事より重要度が高い仕事 j を任されたら、仕事 i をすぐに中断して仕事 j を行います。れんさんは意識が高く且つプロので、行える仕事があれば休むことなく仕事をこなします。

れんさんは、多くの人から「あの仕事もう終わった〜？」と頻繁に聞かれます。しかし あまりにも仕事が多くて、それぞれの仕事が既に終わっているののかどうかよくわかりません＞＜。そこで、それぞれの仕事の完遂時刻を求めて、れんさんを助けてあげてください。但しここでいう仕事の完遂時刻とは、所要時間が 0 になった最初の時刻とします。

入力

M
S1 T1
S2 T2
:
SM TM

1 行目に、れんさんが任される仕事の数 M が与えられる。

2 行目から M 行にかけてそれぞれの仕事の情報が与えられる。このうち i 行目には、仕事 i を任される時刻 Si と 仕事 i の完遂に必要な所要時間 Ti が与えられる。

i < j のとき 仕事 i は 仕事 j よりも重要度は高くなっている。(すなわち、仕事の情報は重要度の高い順に与えられる。)

制約

  • 1 ≦ M ≦ 3 × 105
  • 1 ≦ Si, Ti ≦ 109

部分点

この問題には部分点が設定されている。

  • 全データセットのうち 30％ は、全ての仕事の完遂時刻が 105 以下である。
  • 全データセットのうち 40％ は、M ≦ 1000 を追加で満たす。

出力

M 行に、仕事 1 から順に その仕事の完遂時刻を出力せよ。完遂時刻が 32 bit整数型に収まらない場合があることに注意すること。

入出力例

入力例1

4
3 3
10 1
4 2
2 4

出力例1

6
11
8
12

解説

  • 仕事 1 は時刻 3 から 5 の間行う。よって完遂時刻は 6 となる。
  • 仕事 2 は時刻 10 で行う。よって完遂時刻は 11 となる。
  • 仕事 3 は時刻 6 から 7 の間行う。よって完遂時刻は 8 となる。時刻 4 から 5 の間は、仕事 3 より 重要度が高い仕事 1 があるので この仕事が行われている間は行えない。
  • 仕事 4 は時刻 2 と 時刻 8 から 9, 時刻 11 で行う。よって完遂時刻は 12 となる。

入力例2

8
2 1
3 1
1 1
5 1
1 1
9 1
8 2
7 9

出力例2

3
4
2
6
5
10
11
19

入力例3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

出力例3

2000000000
3000000000
4000000000
5000000000
6000000000