Alexey and Train

题意翻译

### 题目描述 Alexey坐上了一趟火车。假设火车从0这个时刻出发，经过 $n$ 个车站。车站的编号为 1至 $n$ 。火车会在第 $a_i$ 的时刻到达第 $i$ 个站，并在第 $b_i$ 的时刻离开。 由于天气原因，火车从第 $i-1$ 个站到第 $i$ 个站会比原定时间多走 $tm_i$ 的时间（如果 $i$ 为1，那么 $b_0$ 就是火车从始发站离开的时间，并且 $b_0$ 等于0）。 如果满足以下2个条件，火车将会从第 $i$ 个站离开： 1. 在车站至少停留 $\lceil \dfrac{b_i-a_i}{2} \rceil$ 个时刻（向上取整）。 2. 当前时刻 $\ge b_i$ 。 请帮Alexey求出到达第 $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 $ ）。保证 $a_i<b_i$ 。 最后一行由 $n$ 个整数组成，分别为 $tm_1,tm_2,...,tm_n$ （ $0 \le tm_i \le 10^6$ ）。 ### 输出格式 对于每个测试数据，输出一个整数，表示 Alexey火车到达第 $n$ 个车站所需的时间。

题目描述

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 $ .

输入输出格式

输入格式

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 Alexey's arrival at the last station.

输入输出样例

输入样例 #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

输出样例 #1

12
32

说明

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 $ .