Леша едет на поезде. Но вот незадача — из-за плохой погоды поезд едет медленнее, чем должен!
Леша садится на поезд на вокзале. Будем считать, что поезд трогается с вокзала в момент \(0\). Также будем считать, что поезд пройдет через \(n\) станций, пронумерованных от \(1\) по \(n\) в порядке маршрута поезда и Леше нужно попасть на станцию \(n\).
Из маршрутного листа он узнал \(n\) пар целых чисел \((a_i, b_i)\), где \(a_i\) — ожидаемое время прибытия на \(i\)-ю станцию, а \(b_i\) — ожидаемое время отбытия с нее.
Также, принимая во внимание множество факторов, Леша смог рассчитать \(n\) целых чисел \(tm_1, tm_2, \dots, tm_n\), где \(tm_i\) — это то, на сколько больше будет ехать поезд от станции \(i - 1\) до станции \(i\), чем ожидалось. Формально говоря, поезд проедет от станции \(i - 1\) до \(i\) ровно \(a_i - b_{i-1} + tm_i\) времени (при \(i = 1\), за \(b_0\) берется время отбытия от вокзала, равное \(0\)).
Поезд выезжает со станции \(i\), если соблюдаются оба следующих условия:
- он стоит уже хотя бы \(\left\lceil \frac{b_i - a_i}{2} \right\rceil\) времени (деление с округлением вверх);
- текущее время \(\ge b_i\).
Так как Леша потратил все силы на предсказание задержек, помогите ему посчитать время прибытия на станцию \(n\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — время прибытия Леши на последнюю станцию.
Примечание
В первом наборе входных данных Леша сначала пребывает без опоздания на станцию номер \(1\) в момент времени \(a_1 = 2\) (так как \(tm_1 = 0\)). Затем отъезжает с неё в момент времени \(b_1 = 4\). На станцию номер \(2\) он приезжает с опозданием на \(tm_2 = 2\) единицы времени, то есть в \(12\).
Во втором наборе, Леша прибывает на первую станцию с опозданием в \(tm_1 = 1\), то есть в момент \(2\). Далее поезд должен пробыть хотя бы \(\left\lceil \frac{b_1 - a_1}{2} \right\rceil = 2\) единицы времени на станции и отправится не ранее чем в момент \(b_1 = 4\). Таким образом, поезд оправляется с первой станции в момент \(4\).
Разбирая аналогичным образом следующие станции, можно получить, что поезд прибудет на вторую станцию в момент \(9\), а покинет в \(10\); на третью станцию прибудет в \(14\), покинет в \(15\); на четвертую: прибудет в \(22\), покинет в \(23\). И, наконец, прибудет на пятую в \(32\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
2 4
10 12
0 2
5
1 4
7 8
9 10
13 15
19 20
1 2 3 4 5
|
12
32
|