A. Леша и поезд
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Леша едет на поезде. Но вот незадача — из-за плохой погоды поезд едет медленнее, чем должен!

Леша садится на поезд на вокзале. Будем считать, что поезд трогается с вокзала в момент $$$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$$$, если соблюдаются оба следующих условия:

  1. он стоит уже хотя бы $$$\left\lceil \frac{b_i - a_i}{2} \right\rceil$$$ времени (деление с округлением вверх);
  2. текущее время $$$\ge b_i$$$.

Так как Леша потратил все силы на предсказание задержек, помогите ему посчитать время прибытия на станцию $$$n$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество станций.

Далее заданы $$$n$$$ строк, в каждой из которых содержится два целых числа: $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i < b_i \le 10^6$$$). Гарантируется, что $$$b_i < a_{i+1}$$$.

В следующей строке заданы $$$n$$$ целых чисел $$$tm_1, tm_2, \dots, tm_n$$$ ($$$0 \le tm_i \le 10^6$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — время прибытия Леши на последнюю станцию.

Пример
Входные данные
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
Примечание

В первом наборе входных данных Леша сначала пребывает без опоздания на станцию номер $$$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$$$.