← 返回题目列表

AtCoder · awc0044_a

A. 补充水

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥正在管理一个花坛。今天的任务是将水龙头打来的水倒入每个花盆中。

有 N 花盆在花坛中排列成一排, i第-个花盆最多可容纳 C_i 升水。目前, i第花盆已包含 S_i 升水。

高桥获取 M 升水从水龙头出来并装在桶里。他按顺序参观花盆 1, 2, \ldots, N,对每个执行以下操作:

  • 花盆用 i,倒入花盆 i 水量等于 较小 锅的剩余容量 C_i - S_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
  • 第一行包含一个整数 N 代表花盆的数量和一个整数 M 代表新配制的水量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每个花盆的信息。
  • 的 (1 + i)第行包含最大容量 C_i 的 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