分数: 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