← 返回题目列表

Codeforces · 883/K

K. 道路拓宽

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

S市市长就是讨厌树木和草坪。它们占据了如此大的空间,它们占据的地方可能有一条路!

市长认为,由于没有人需要草坪,可以大大拓宽城市的主要街道之一。此外,这可能有助于减少街道上时不时发生的汽车拥堵。

街道从左到右被分成n个等长的部分,第i部分由两个整数表征:道路宽度si和草坪宽度gi。

对于 n 个部分中的每一个,市长应决定要拆除的草坪的大小。对于第 i 部分,他可以将草坪宽度减少整数 xi (0 ≤ xi ≤ gi)。之后,第 i 部分的新道路宽度将等于 s'i = si + xi,新草坪宽度将等于 g'i = gi - xi。

一方面,市长希望拆除尽可能多的草坪(并用道路代替)。另一方面,他也不希望道路急剧拓宽或变窄,以免引发车祸。为了避免这种情况,市长决定连续部分的道路宽度最多相差 1,即对于每个 i (1 ≤ i < n),不等式 |s'i + 1 - s'i| ≤ 1 应成立。最初这个条件可能不成立。

您需要找到市长将根据他的计划摧毁的草坪的总宽度。

输入

第一行包含整数 n (1 ≤ n ≤ 2·105) — 街道部分的数量。

以下 n 行每行包含两个整数 si, gi (1 ≤ si ≤ 106, 0 ≤ gi ≤ 106) — 当前道路宽度和街道第 i 部分草坪的宽度。

输出

在第一行中打印将被移除的草坪的总宽度。

在第二行中打印 n 个整数 s'1, s'2, ..., s'n (si ≤ s'i ≤ si + gi) — 从第一部分开始到最后一部分的新道路宽度。

如果无解,则在第一行打印唯一的整数-1。

示例

输入 #1

3
4 5
4 5
4 10

输出 #1

16
9 9 10

输入 #2

4
1 100
100 1
1 100
100 1

输出 #2

202
101 101 101 101

输入 #3

3
1 1
100 100
1 1

输出 #3

-1