题目描述

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$ 个车站所需的时间。

样例

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