Вы пригласили \(n\) гостей на вечеринку! Вы планируете сделать один или несколько кругов из стульев. На некоторые стулья сядут гости. На каждом стуле может сидеть не более одного гостя.
Так как гости немного стеснительные, \(i\)-й из них хочет иметь хотя бы \(l_i\) свободных стульев слева от себя, и хотя бы \(r_i\) свободных стульев справа. Направления «влево» и «вправо» отсчитываются в предположении, что все гости смотрят в центр своего круга. Обратите внимание, что если в круге сидит только один гость, то среди \(l_i\) стульев слева и \(r_i\) стульев справа могут быть пересечения.
Какое минимальное общее количество стульев вам понадобится?
Выходные данные
Выведите единственное число — минимальное число стульев.
Примечание
Во втором примере оптимальный ответ является единственным и состоит из двух кругов: круг с \(5\) стульями для гостей \(1\) и \(2\), и круг с \(10\) стульями для гостей \(3\) и \(4\).
Обратите внимание, в третьем примере для единственного достаточно одного круга с семью стульями. В самом деле, слева от него должно быть хотя бы 5 стульев, а справа хотя бы 6, до следующего человека. В данном случае это сам гость. Следовательно, для семи стульев оба условия удовлетворены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
1 1
1 1
|
6
|
|
2
|
4
1 2
2 1
3 5
5 3
|
15
|
|
3
|
1
5 6
|
7
|