A - Refilling Water Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は花壇の管理をしています。今日の仕事は、水道から汲んできた水をそれぞれの植木鉢に注ぐことです。

花壇には N 個の植木鉢が一列に並んでおり、i 番目の植木鉢には最大 C_i リットルの水が入ります。現在、i 番目の植木鉢にはすでに S_i リットルの水が入っています。

高橋君は水道から新たに M リットルの水を汲み、バケツに入れて持ち歩きます。植木鉢 1, 2, \ldots, N の順に、次の操作を行います。

  • 植木鉢 i について、その植木鉢の空き容量 C_i - S_i リットルと、現在バケツに残っている水の量のうち、小さい方 に等しい量の水を植木鉢 i に注ぐ。注いだ分だけバケツの水は減り、植木鉢 i に入っている水の量はその分だけ増える。

すべての植木鉢について操作を終えた後、バケツに水が残っていればその水は捨てます。

すべての操作が終わった後の、各植木鉢に入っている水の量を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 10^{18}
  • 1 \leq C_i \leq 10^9
  • 0 \leq S_i \leq C_i
  • 入力はすべて整数である。

入力

N M
C_1 S_1
C_2 S_2
\vdots
C_N S_N
  • 1 行目には、植木鉢の個数を表す整数 N と、新たに用意した水の量を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各植木鉢の情報が与えられる。
  • 1 + i 行目には、i 番目の植木鉢の最大容量 C_i と、現在入っている水の量 S_i が、スペース区切りで与えられる。

出力

N 行出力してください。i 行目には、すべての操作が終わった後に i 番目の植木鉢に入っている水の量を出力してください。

入力例 1

3 8
10 3
8 5
6 2

出力例 1

10
6
2

入力例 2

5 100
10 5
20 20
15 3
8 0
12 7

出力例 2

10
20
15
8
12

入力例 3

8 1000000000000
1000000000 0
500000000 200000000
1000000000 1000000000
300000000 100000000
700000000 0
400000000 400000000
600000000 150000000
200000000 50000000

出力例 3

1000000000
500000000
1000000000
300000000
700000000
400000000
600000000
200000000

Score : 266 pts

Problem Statement

Takahashi is managing a flower bed. Today's task is to pour water fetched from the faucet into each flower pot.

There are N flower pots arranged in a row in the flower bed, and the i-th flower pot can hold a maximum of C_i liters of water. Currently, the i-th flower pot already contains S_i liters of water.

Takahashi fetches M liters of water from the faucet and carries it in a bucket. He visits the flower pots in the order 1, 2, \ldots, N, performing the following operation for each:

  • For flower pot i, pour into flower pot i an amount of water equal to the smaller of the remaining capacity of the pot C_i - S_i liters and the amount of water currently remaining in the bucket. The water in the bucket decreases by the amount poured, and the amount of water in flower pot i increases by that same amount.

After finishing the operation for all flower pots, if there is any water remaining in the bucket, it is discarded.

Determine the amount of water in each flower pot after all operations are completed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 10^{18}
  • 1 \leq C_i \leq 10^9
  • 0 \leq S_i \leq C_i
  • All input values are integers.

Input

N M
C_1 S_1
C_2 S_2
\vdots
C_N S_N
  • The first line contains an integer N representing the number of flower pots and an integer M representing the amount of newly prepared water, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each flower pot is given.
  • The (1 + i)-th line contains the maximum capacity C_i of the i-th flower pot and the current amount of water S_i, separated by a space.

Output

Print N lines. On the i-th line, print the amount of water in the i-th flower pot after all operations are completed.

Sample Input 1

3 8
10 3
8 5
6 2

Sample Output 1

10
6
2

Sample Input 2

5 100
10 5
20 20
15 3
8 0
12 7

Sample Output 2

10
20
15
8
12

Sample Input 3

8 1000000000000
1000000000 0
500000000 200000000
1000000000 1000000000
300000000 100000000
700000000 0
400000000 400000000
600000000 150000000
200000000 50000000

Sample Output 3

1000000000
500000000
1000000000
300000000
700000000
400000000
600000000
200000000