Solo

Alice 和 Bob 准备 solo 一场算法竞赛。

比赛一共有 $n$ 个题，编号为 $1,2....,n$，对于第 $i$ 道题，Alice 需要 $a[i]$ 分钟写出一份正确的代码，Bob 需要 $b[i]$ 分钟写出一份正确的代码。

比赛规则为
1. 每道题第一个通过的人积 1 分，如果两人同时 AC 该题，只有 Alice 得分。
2. 比赛时长为 $10 ^ {18}$ 分钟。

Alice 和 Bob 的比赛策略都满足：决定要去做某道题后，会一直解决该题，直到自己或者对手 AC 此题，如果对手 AC 该题，则会立即放弃这题。

Bob 写完一份正确的代码后会立即提交，但 Alice 写完一份正确的代码，可以先暂时不交题，等之后再交（交题的时间忽略不计，任何时间都可以交题）。

另外 Alice 知道 Bob 是按 $1,2,....,n$ 的顺序来依次做题，知道每道题自己需要的时间和 Bob 需要的时间（即 $a$ 序列和 $b$ 序列）。

输出 Alice 最优策略下最多得几分。

Alice 和 Bob 想题都不需要时间。

第一行一个整数 $t(1 \leq t \leq 10)$ 表示 $t$ 组数据。

每组数据第一行一个整数 $n (1 \leq n \leq 2000)$ 表示题数。

第二行 $n$ 个整数，表示 $a[1],a[2],...a[n](1 \leq a[i] \leq 1000000000)$。

第三行 $n$ 个整数，表示 $b[1],b[2],...b[n](1 \leq b[i] \leq 1000000000)$。

保证至多只有一组数据 $n>100$。

对于每组数据，一行一个整数表示答案。

2
6
6 6 6 6 6 6
1 1 1 1 1 1
3
1 2 3
5 1 1

1
3

样例解释
Case 1 开场直接 rush 最后一题。
Case 2 [0,1) 写掉第一题，第 5 分钟交；[1,3) 写第二题第 6 分钟交，[3,6) 写第三题第 6 分钟交。

2020 年百度之星·程序设计大赛 - 初赛二