J. One Percent
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ types of coins with you. There are $$$c_i$$$ many coins of the $$$i^{\text{th}}$$$ type, each having value $$$v_i$$$. You are interested in knowing the smallest fraction $$$p$$$ such that $$$p$$$ fraction of the coins hold at least $$$1-p$$$ fraction of the total value of all the coins.

More formally, let $$$C = \sum_{i=1}^{n}c_i$$$ and $$$V = \sum_{i=1}^{n}c_i \cdot v_i$$$. You have to find the smallest integer $$$x$$$ such that there exists a subset of $$$x$$$ coins which have at least $$$\left(1-\frac{x}{C}\right)\cdot V$$$ value.

You have to output the integer $$$x$$$.

Input

The first line of each test contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of types of coins.

The second line of each test case contains $$$n$$$ space-separated integers $$$c_i$$$ ($$$1 \le c_i \le 1000$$$) — the number of coins of the $$$i^{\text{th}}$$$ type.

The third line of each test case contains $$$n$$$ space-separated integers $$$v_i$$$ ($$$1 \le v_i \le 1000$$$) — the value of one coin of the $$$i^{\text{th}}$$$ type.

There are no guarantees about the sum of $$$n$$$ over all test cases.

Output

For each test case, output one line containing a single integer $$$x$$$ — the smallest integer as described above.

Example
Input
3
1
1000
1
4
37 37 37 37
1 2 4 2
1
1
1000
Output
500
61
1
Note

For test case 1, there is one type of coin, $$$1000$$$ in number and $$$1$$$ each in value. Here, $$$C = 1000$$$ and $$$V = 1000$$$. If we choose $$$x = 500$$$, we can select a subset of $$$500$$$ coins of type 1 each having value $$$1$$$ (total value is $$$500$$$), so that $$$500 \ge \left(1 - \frac{500}{1000}\right)\cdot 1000$$$ is true. It can be shown that $$$x \lt 500$$$ is not possible, so the minimum answer is $$$500$$$.

For test case 2, there are the following types of coins:

  1. $$$37$$$ many, each having value $$$1$$$.
  2. $$$37$$$ many, each having value $$$2$$$.
  3. $$$37$$$ many, each having value $$$4$$$.
  4. $$$37$$$ many, each having value $$$2$$$.
Here, $$$C = 148$$$ and $$$V = 333$$$. If we choose $$$x = 61$$$, we can select a subset of $$$61$$$ coins ($$$13$$$ of type 2, $$$37$$$ of type 3, and $$$11$$$ of type 4) having total value $$$196$$$, so that $$$196 \ge \left(1 - \frac{61}{148}\right) \cdot 333$$$ is true. It can be shown that $$$x \lt 61$$$ is not possible, so the minimum answer is $$$61$$$.