Pursuit

题意翻译

#### 1、题目描述翻译 你和你的朋友伊利亚正在参加由多个阶段组成的编程竞赛。 对于每个阶段，你和伊利亚都会获得一个分数，保证为 $0$ 到 $100$ 之间的整数。并且，每个人获得的分数都是相互独立的，不受对方影响。 总分是这样计算的：设当前已进行 $k$ 个阶段，则你的总分为最高的 $k-\left\lfloor k\div4\right\rfloor $个阶段得分之和。其中 $\left\lfloor a\right\rfloor$ 代表 $a$ 向下取整（不大于 $a$ 的最大整数）。 现在，这个竞赛已进行了 $n$ 个阶段，你也知道这些阶段中，两个人获得的分数。但比赛仍在进行。请问：理论上，至少再过多少个阶段，你的总分才能超过伊利亚？如果你的总分已经超过了她，请输出 `0`。 #### 2、输入格式翻译 第一行一个整数 $t$（$1\le t\le1000$），代表测试数据组数。 对于每个测试数据，第一行一个整数 $n$（$1\le n\le10^5$），代表已经进行了 $n$ 个阶段。 接下来有两行，每行都有 $n$ 个数。第一行代表你的每个阶段的得分，第二行代表伊利亚每个阶段的得分。 #### 3、输出格式翻译 对于每个测试数据，输出一行，一个整数，即问题所求的答案。如果你的总分已经超过了她，请输出 `0`。 Translated by [dengzijun](https://www.luogu.com.cn/user/387836)

题目描述

You and your friend Ilya are participating in an individual programming contest consisting of multiple stages. A contestant can get between $ 0 $ and $ 100 $ points, inclusive, for each stage, independently of other contestants. Points received by contestants in different stages are used for forming overall contest results. Suppose that $ k $ stages of the contest are completed. For each contestant, $ k - \lfloor \frac{k}{4} \rfloor $ stages with the highest scores are selected, and these scores are added up. This sum is the overall result of the contestant. (Here $ \lfloor t \rfloor $ denotes rounding $ t $ down.) For example, suppose $ 9 $ stages are completed, and your scores are $ 50, 30, 50, 50, 100, 10, 30, 100, 50 $ . First, $ 7 $ stages with the highest scores are chosen — for example, all stages except for the $ 2 $ -nd and the $ 6 $ -th can be chosen. Then your overall result is equal to $ 50 + 50 + 50 + 100 + 30 + 100 + 50 = 430 $ . As of now, $ n $ stages are completed, and you know the points you and Ilya got for these stages. However, it is unknown how many more stages will be held. You wonder what the smallest number of additional stages is, after which your result might become greater than or equal to Ilya's result, at least in theory. Find this number!

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of completed stages. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 100 $ ) — your points for the completed stages. The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0 \le b_i \le 100 $ ) — Ilya's points for the completed stages. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print a single integer — the smallest number of additional stages required for your result to be able to become greater than or equal to Ilya's result. If your result is already not less than Ilya's result, print $ 0 $ .

输入输出样例

输入样例 #1

5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64

输出样例 #1

0
1
3
4
2

说明

In the first test case, you have scored $ 100 $ points for the first stage, while Ilya has scored $ 0 $ . Thus, your overall result ( $ 100 $ ) is already not less than Ilya's result ( $ 0 $ ). In the second test case, you have scored $ 0 $ points for the first stage, while Ilya has scored $ 100 $ . A single stage with an opposite result is enough for both your and Ilya's overall scores to become equal to $ 100 $ . In the third test case, your overall result is $ 30 + 40 + 50 = 120 $ , while Ilya's result is $ 100 + 100 + 100 = 300 $ . After three additional stages your result might become equal to $ 420 $ , while Ilya's result might become equal to $ 400 $ . In the fourth test case, your overall result after four additional stages might become equal to $ 470 $ , while Ilya's result might become equal to $ 400 $ . Three stages are not enough.