English · Original
Chinese · Translation
Formal · Original
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_.
<center></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_.
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.
## Input
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.
## Output
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.
[samples]
城市S的市长非常讨厌树木和草坪。它们占用了太多空间，而这些地方本可以用来修路！
市长认为，城市的一条主干道可以通过拆除没人需要的草坪来显著拓宽，这还有助于缓解道路上时有发生的交通拥堵。
这条街道被划分为 #cf_span[n] 个等长的部分，从左到右编号。第 #cf_span[i] 个部分由两个整数描述：道路宽度 #cf_span[si] 和草坪宽度 #cf_span[gi]。
对于每个 #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]。
一方面，市长希望尽可能多地拆除草坪（并用道路替代）；另一方面，他不希望道路宽度出现急剧的变宽或变窄，以免引发交通事故。为此，他规定：相邻部分的道路宽度之差不得超过 #cf_span[1]，即对每个 #cf_span[i]（#cf_span[1 ≤ i < n]），必须满足不等式 #cf_span[|s'i + 1 - s'i| ≤ 1]。初始状态下，这一条件可能不成立。
你需要找出市长计划中将被拆除的草坪总宽度。
第一行包含整数 #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] 个部分当前的道路宽度和草坪宽度。
第一行输出将被拆除的草坪总宽度。
第二行输出 #cf_span[n] 个整数 #cf_span[s'1, s'2, ..., s'n]（#cf_span[si ≤ s'i ≤ si + gi]）——从第一部分到最后一部分的新道路宽度。
如果没有可行解，请在第一行仅输出整数 _-1_。
## Input
第一行包含整数 #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] 个部分当前的道路宽度和草坪宽度。
## Output
第一行输出将被拆除的草坪总宽度。第二行输出 #cf_span[n] 个整数 #cf_span[s'1, s'2, ..., s'n]（#cf_span[si ≤ s'i ≤ si + gi]）——从第一部分到最后一部分的新道路宽度。如果没有可行解，请在第一行仅输出整数 _-1_。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of street parts.
For 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 $.
Let $ x_i \in \mathbb{Z} $ be the lawn width demolished on part $ i $, with $ 0 \leq x_i \leq g_i $.
Let $ s_i' = s_i + x_i $ be the new road width on part $ i $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq s_i \leq 10^6 $, $ 0 \leq g_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
3. $ s_i \leq s_i' \leq s_i + g_i $ for all $ i \in \{1, \dots, n\} $
4. $ |s_{i+1}' - s_i'| \leq 1 $ for all $ i \in \{1, \dots, n-1\} $
**Objective**
Maximize $ \sum_{i=1}^n x_i = \sum_{i=1}^n (s_i' - s_i) $, subject to the above constraints.
Output the maximum total demolished lawn width and the sequence $ (s_1', \dots, s_n') $.
If no valid sequence exists, output $-1$.
API Response (JSON)
{
"problem": {
"name": "K. Road Widening",
"description": {
"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! The Mayor thinks that one of the main city streets could be considerably widene",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF883K"
},
"statements": [
{
"statement_type": "Markdown",
"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 widene...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "城市S的市长非常讨厌树木和草坪。它们占用了太多空间，而这些地方本可以用来修路！\n\n市长认为，城市的一条主干道可以通过拆除没人需要的草坪来显著拓宽，这还有助于缓解道路上时有发生的交通拥堵。\n\n这条街道被划分为 #cf_span[n] 个等长的部分，从左到右编号。第 #cf_span[i] 个部分由两个整数描述：道路宽度 #cf_span[si] 和草坪宽度 #cf_span[gi]。\n\n对于每个 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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 ro...",
"is_translate": false,
"language": "Formal"
}
]
}