CF1501A.Alexey and Train

Alexey is travelling on a train. Unfortunately, due to the bad weather, the train moves slower that it should!

Alexey took the train at the railroad terminal. Let's say that the train starts from the terminal at the moment $0$. Also, let's say that the train will visit $n$ stations numbered from $1$ to $n$ along its way, and that Alexey destination is the station $n$.

Alexey learned from the train schedule $n$ integer pairs $(a_i, b_i)$ where $a_i$ is the expected time of train's arrival at the $i$-th station and $b_i$ is the expected time of departure.

Also, using all information he has, Alexey was able to calculate $n$ integers $tm_1, tm_2, \dots, tm_n$ where $tm_i$ is the extra time the train need to travel from the station $i - 1$ to the station $i$. Formally, the train needs exactly $a_i - b_{i-1} + tm_i$ time to travel from station $i - 1$ to station $i$ (if $i = 1$ then $b_0$ is the moment the train leave the terminal, and it's equal to $0$).

The train leaves the station $i$, if both conditions are met:

1. it's on the station for at least $\left\lceil \frac{b_i - a_i}{2} \right\rceil$ units of time (division with ceiling);
2. current time $\ge b_i$.

Since Alexey spent all his energy on prediction of time delays, help him to calculate the time of arrival at the station $n$.

阿列克谢正在乘坐一列火车。不幸的是，由于天气恶劣，火车行驶速度比预期更慢！

阿列克谢在铁路终点站登上了火车。假设火车在时刻 $0$ 从终点站出发。此外，假设火车沿途将依次停靠 $n$ 个车站，编号为 $1$ 到 $n$，而阿列克谢的目的地是第 $n$ 号车站。

阿列克谢查阅了列车时刻表，获得了 $n$ 个整数对 $(a_i, b_i)$，其中 $a_i$ 表示火车预计到达第 $i$ 个车站的时刻，$b_i$ 表示火车预计离开第 $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$ 号车站的时刻。

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \le n \le 100$) — the number of stations.

Next $n$ lines contain two integers each: $a_i$ and $b_i$ ($1 \le a_i \lt b_i \le 10^6$). It's guaranteed that $b_i \lt a_{i+1}$.

Next line contains $n$ integers $tm_1, tm_2, \dots, tm_n$ ($0 \le tm_i \le 10^6$).

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 车站的数量。

接下来的 $n$ 行每行包含两个整数：$a_i$ 和 $b_i$（$1 \le a_i \lt b_i \le 10^6$）。保证 $b_i \lt a_{i+1}$。

下一行包含 $n$ 个整数 $tm_1, tm_2, \dots, tm_n$（$0 \le tm_i \le 10^6$）。

For each test case, print one integer — the time of Alexey's arrival at the last station.

对于每个测试用例，输出一个整数——Alexey 到达最后一个车站的时间。

In the first test case, Alexey arrives at station $1$ without any delay at the moment $a_1 = 2$ (since $tm_1 = 0$). After that, he departs at moment $b_1 = 4$. Finally, he arrives at station $2$ with $tm_2 = 2$ extra time, or at the moment $12$.

In the second test case, Alexey arrives at the first station with $tm_1 = 1$ extra time, or at moment $2$. The train, from one side, should stay at the station at least $\left\lceil \frac{b_1 - a_1}{2} \right\rceil = 2$ units of time and from the other side should depart not earlier than at moment $b_1 = 4$. As a result, the trains departs right at the moment $4$.

Using the same logic, we can figure out that the train arrives at the second station at the moment $9$ and departs at the moment $10$; at the third station: arrives at $14$ and departs at $15$; at the fourth: arrives at $22$ and departs at $23$. And, finally, arrives at the fifth station at $32$.

在第一个测试用例中，Alexey 在时刻 $a_1 = 2$（因为 $tm_1 = 0$）准时抵达第 1 号车站。随后，他在时刻 $b_1 = 4$ 离开该站。最终，他于时刻 $12$ 抵达第 2 号车站，比原计划多花了 $tm_2 = 2$ 单位时间。

在第二个测试用例中，Alexey 比原计划多花 $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$ 抵达第五站。