CF883K.Road Widening

Mayor of city S just hates trees and lawns. They take so much space and there could be a road on the place they occupy!

The Mayor thinks that one of the main city streets could be considerably widened on account of lawn nobody needs anyway. Moreover, that might help reduce the car jams which happen from time to time on the street.

The street is split into n equal length parts from left to right, the i-th part is characterized by two integers: width of road s__i and width of lawn g__i.

For each of n parts the Mayor should decide the size of lawn to demolish. For the i-th part he can reduce lawn width by integer x__i (0 ≤ x__i ≤ g__i). After it new road width of the i-th part will be equal to s'i = s__i + x__i and new lawn width will be equal to g'i = g__i - x__i.

On the one hand, the Mayor wants to demolish as much lawn as possible (and replace it with road). On the other hand, he does not want to create a rapid widening or narrowing of the road, which would lead to car accidents. To avoid that, the Mayor decided that width of the road for consecutive parts should differ by at most 1, i.e. for each i (1 ≤ i < n) the inequation |s'i + 1 - s'i| ≤ 1 should hold. Initially this condition might not be true.

You need to find the the total width of lawns the Mayor will destroy according to his plan.

城市 S 的市长极其讨厌树木和草坪。它们占据了太多空间，而这些地方本可以修建道路！

市长认为，城市的一条主干道可以通过拆除无人需要的草坪而显著拓宽。此外，这或许还能缓解该街道上不时发生的交通拥堵。

这条街道从左到右被划分为 $n$ 个等长的部分，第 $i$ 个部分由两个整数刻画：道路宽度 $s_i$ 和草坪宽度 $g_i$。

对于这 $n$ 个部分中的每一个，市长需决定拆除多少草坪。对第 $i$ 个部分，他可将草坪宽度减少一个整数 $x_i$（其中 $0 \le x_i \le g_i$）。拆除后，该部分新的道路宽度为 $s'_i = s_i + x_i$，新的草坪宽度为 $g'_i = g_i - x_i$。

一方面，市长希望尽可能多地拆除草坪（并将其替换为道路）；另一方面，他又不希望道路在相邻路段之间突然变宽或变窄，以免引发交通事故。为避免这种情况，市长规定：任意两个相邻路段的道路宽度之差的绝对值至多为 $1$，即对每个 $i$（$1 \le i < n$），需满足不等式 $|s'_{i+1} - s'_i| \le 1$。初始状态下，该条件可能并不成立。

你需要根据市长的规划，计算出他总共将拆除的草坪总宽度。

The first line contains integer n (1 ≤ n ≤ 2·105) — number of parts of the street.

Each of the following n lines contains two integers s__i, g__i (1 ≤ s__i ≤ 106, 0 ≤ g__i ≤ 106) — current width of road and width of the lawn on the i-th part of the street.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 街道的段数。

接下来的 $n$ 行中，每行包含两个整数 $s_i$、$g_i$（$1 \leq s_i \leq 10^6$，$0 \leq g_i \leq 10^6$）—— 第 $i$ 段街道当前的道路宽度和草坪宽度。

In the first line print the total width of lawns which will be removed.

In the second line print n integers s'1, s'2, ..., s'n (s__i ≤ s'i ≤ s__i + g__i) — new widths of the road starting from the first part and to the last.

If there is no solution, print the only integer -1 in the first line.

第一行输出将被移除的草坪总宽度。

第二行输出 $n$ 个整数 $s'_1,\ s'_2,\ \dots,\ s'_n$（满足 $s_i \leq s'_i \leq s_i + g_i$），表示从道路第一段到最后一段的新宽度。

若无解，则第一行仅输出整数 $-1$。