Alexey 正在火车上旅行。不幸的是,由于天气恶劣,火车的行驶速度比应有的速度慢!
阿列克谢在火车站乘坐火车。假设火车此时从终点站出发$$$0$$$。另外,假设火车沿途将经过从 $$$1$$$ 到 $$$n$$$ 编号的 $$$n$$$ 车站,而 Alexey 的目的地是 $$$n$$$ 车站。
Alexey 从火车时刻表 $$$n$$$ 整数对 $$$(a_i, b_i)$$$ 中得知,其中 $$$a_i$$$ 是火车到达第 $$$i$$$ 个车站的预计时间,$$$b_i$$$ 是预计出发时间。
此外,利用他掌握的所有信息,Alexey 能够计算出 $$$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$$$。
由于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$$$)。保证 $$$b_i < a_{i+1}$$$。
下一行包含 $$$n$$$ 整数 $$$tm_1, tm_2, \dots, tm_n$$$ ($$$0 \le tm_i \le 10^6$$$)。
输出
对于每个测试用例,打印一个整数 - Alexey 到达最后一站的时间。
示例
输入 #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
注意
在第一个测试用例中,Alexey 在 $$$a_1 = 2$$$ 时刻到达车站 $$$1$$$,没有任何延迟(因为 $$$tm_1 = 0$$$)。之后,他在 $$$b_1 = 4$$$ 时刻出发。最后,他以 $$$tm_2 = 2$$$ 额外时间到达车站 $$$2$$$,或者此时 $$$12$$$。
在第二个测试用例中,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$$$。