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