You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

有 $n$ 个关卡，第 $i$ 个关卡有两个参数 $a_i$ 和 $b_i$。

从第 $1$ 个关卡开始，假设你面对第 $i$ 个关卡时有 $x$ 能量：

• 如果 $x<a_i$，那么你无法通过第 $i$ 个关卡；
• 如果 $x\geq a_i$，那么你消耗 $a_i$ 点能量并通过第 $i$ 个关卡，通过第 $i$ 个关卡后奖励你 $\min(x-a_i,b_i)$ 点能量，能量变为 $x-a_i+\min(x-a_i,b_i)$；
• 如果 $i<n$，接下来面对第 $i+1$ 个关卡。

求你的初始能量至少是多少，才能通过所有关卡。

共有 $T$ 组数据。

格式

输入格式

第一行包含一个整数 $T$，表示数据的组数。

对于每组数据：

第一行包含一个整数 $n$，表示关卡的数量。

第二行包含 $n$ 个整数 $a_i$，含义与题目描述相同。

第三行包含 $n$ 个整数 $b_i$，含义与题目描述相同。

输出格式

对于每组数据，在单独的一行中输出一个整数，表示如果要通过所有关卡，初始能量的最小值。

样例

样例输入 #1

2
10
6 13 9 9 2 3 8 99 23 1
44 2 12 1 4 6 2 7 11 100
10
1 3 9 1 5 11 24 7 93 200
1 5 9 52 23 1 6 8 9 1000000000

样例输出 #1

95
240

数据规模

对于 $30\%$ 的数据，$n\leq 100$，$a_i,b_i\leq 100$。

对于 $100\%$ 的数据，$1\leq T\leq 10$，$1\leq n\leq 10^5$，$1\leq a_i,b_i\leq 10^9$。