× 如果遇到编译错误信息中包含大量 \"5MhZ4\" 之类,请更换最新 Chrome/Firefox/Edge 浏览器再试

Solo

Accepts: 167
Submissions: 493
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
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 想题都不需要时间。
Input
第一行一个整数 $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$。
Output
对于每组数据,一行一个整数表示答案。
Sample Input
2
6
6 6 6 6 6 6
1 1 1 1 1 1
3
1 2 3
5 1 1
Sample Output
1
3

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