{"raw_statement":[{"iden":"statement","content":"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!\n\nThe 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.\n\nThe 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_.\n\n<center>![image](https://espresso.codeforces.com/1e351a64cc735b32c3ed5bd9304d0d528a12a83e.png)</center>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_.\n\nOn 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.\n\nYou need to find the the total width of lawns the Mayor will destroy according to his plan."},{"iden":"input","content":"The first line contains integer _n_ (1 ≤ _n_ ≤ 2·105) — number of parts of the street.\n\nEach 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."},{"iden":"output","content":"In the first line print the total width of lawns which will be removed.\n\nIn 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.\n\nIf there is no solution, print the only integer _\\-1_ in the first line."},{"iden":"examples","content":"Input\n\n3\n4 5\n4 5\n4 10\n\nOutput\n\n16\n9 9 10 \n\nInput\n\n4\n1 100\n100 1\n1 100\n100 1\n\nOutput\n\n202\n101 101 101 101 \n\nInput\n\n3\n1 1\n100 100\n1 1\n\nOutput\n\n\\-1"}],"translated_statement":[{"iden":"statement","content":"城市S的市长非常讨厌树木和草坪。它们占用了太多空间，而这些地方本可以用来修路！\n\n市长认为，城市的一条主干道可以通过拆除没人需要的草坪来显著拓宽，这还有助于缓解道路上时有发生的交通拥堵。\n\n这条街道被划分为 #cf_span[n] 个等长的部分，从左到右编号。第 #cf_span[i] 个部分由两个整数描述：道路宽度 #cf_span[si] 和草坪宽度 #cf_span[gi]。\n\n对于每个 #cf_span[n] 个部分，市长需要决定拆除多少草坪。对于第 #cf_span[i] 个部分，他可以将草坪宽度减少整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ gi]）。拆除后，第 #cf_span[i] 个部分的新道路宽度变为 #cf_span[s'i = si + xi]，新草坪宽度变为 #cf_span[g'i = gi - xi]。\n\n一方面，市长希望尽可能多地拆除草坪（并用道路替代）；另一方面，他不希望道路宽度出现急剧的变宽或变窄，以免引发交通事故。为此，他规定：相邻部分的道路宽度之差不得超过 #cf_span[1]，即对每个 #cf_span[i]（#cf_span[1 ≤ i < n]），必须满足不等式 #cf_span[|s'i + 1 - s'i| ≤ 1]。初始状态下，这一条件可能不成立。\n\n你需要找出市长计划中将被拆除的草坪总宽度。\n\n第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——街道的部分数量。\n\n接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[si, gi]（#cf_span[1 ≤ si ≤ 106], #cf_span[0 ≤ gi ≤ 106]）——第 #cf_span[i] 个部分当前的道路宽度和草坪宽度。\n\n第一行输出将被拆除的草坪总宽度。\n\n第二行输出 #cf_span[n] 个整数 #cf_span[s'1, s'2, ..., s'n]（#cf_span[si ≤ s'i ≤ si + gi]）——从第一部分到最后一部分的新道路宽度。\n\n如果没有可行解，请在第一行仅输出整数 _-1_。"},{"iden":"input","content":"第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——街道的部分数量。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[si, gi]（#cf_span[1 ≤ si ≤ 106], #cf_span[0 ≤ gi ≤ 106]）——第 #cf_span[i] 个部分当前的道路宽度和草坪宽度。"},{"iden":"output","content":"第一行输出将被拆除的草坪总宽度。第二行输出 #cf_span[n] 个整数 #cf_span[s'1, s'2, ..., s'n]（#cf_span[si ≤ s'i ≤ si + gi]）——从第一部分到最后一部分的新道路宽度。如果没有可行解，请在第一行仅输出整数 _-1_。"},{"iden":"examples","content":"输入34 54 54 10输出169 9 10 输入41 100100 11 100100 1输出202101 101 101 101 输入31 1100 1001 1输出-1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of street parts.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ s_i \\in \\mathbb{Z}^+ $ and $ g_i \\in \\mathbb{Z}_{\\geq 0} $ denote the initial road width and lawn width of part $ i $.  \nLet $ x_i \\in \\mathbb{Z} $ be the lawn width demolished on part $ i $, with $ 0 \\leq x_i \\leq g_i $.  \nLet $ s_i' = s_i + x_i $ be the new road width on part $ i $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq s_i \\leq 10^6 $, $ 0 \\leq g_i \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ s_i \\leq s_i' \\leq s_i + g_i $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ |s_{i+1}' - s_i'| \\leq 1 $ for all $ i \\in \\{1, \\dots, n-1\\} $\n\n**Objective**  \nMaximize $ \\sum_{i=1}^n x_i = \\sum_{i=1}^n (s_i' - s_i) $, subject to the above constraints.  \nOutput the maximum total demolished lawn width and the sequence $ (s_1', \\dots, s_n') $.  \nIf no valid sequence exists, output $-1$.","simple_statement":null,"has_page_source":false}