单点时限: 2.0 sec
内存限制: 512 MB
Rachel is travelling on a train. Unfortunately, due to the bad weather, the train moves slower that it should!
Rachel 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 Rachel’s destination is the station $n$.
Rachel 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, Rachel was able to calculate $n$ integers $tm_1,tm_2,\cdots,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:
Since Rachel spent all his energy on prediction of time delays, help her to calculate the time of arrival at the station $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 < b_i \le 10^6$). It’s guaranteed that $b_i < a_{i+1}$.
Next line contains $n$ integers $tm_1, tm_2, \dots, tm_n$ ($0 \le tm_i \le 10^6$).
For each test case, print one integer — the time of Rachel’s arrival at the last station.
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
In the first test case, Rachel arrives at station $1$ without any delay at the moment $a_1=2$ (since $tm_1=0$). After that, she departs at moment $b_1=4$. Finally, she arrives at station $2$ with $tm_2=2$ extra time, or at the moment $12$.
In the second test case, Rachel 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$.