This page is still under construction.

Parts of this page are still being built. What you see may change.

Supercomputer

Time limit1sMemory limit256 MB

Summary
Choose an order of N programs and one program to shorten to 1 hour, minimizing the maximum lateness relative to deadlines.
Level

Medium6 of 10

Topics
Greedy, Sorting, Binary search, Implementation
Solved
No attempts yet

Problem

You must run an experiment on a supercomputer by executing N programs sequentially.

The programs are numbered 1 through N. Program i runs for H[i] hours, and its desired deadline is D[i] hours from now.

Since there are N programs, there are N! possible execution orders.

Let C[i] be the time, in hours from now, at which program i finishes. Define max(0, C[i] - D[i]) as the "lateness" of program i. If a program finishes no later than its desired deadline, its lateness is 0.

The "maximum lateness" is the maximum lateness among the N programs.

This supercomputer has an unusual feature: you can designate exactly one of the N programs as the "top priority target", and that program runs in exactly 1 hour.

For example, let N = 3, H = [2, 4, 6], D = [3, 5, 8].

If you run programs 1 through 3 in that order and designate program 3 to run in 1 hour, then program 1 starts now and finishes 2 hours later (C[1] = 2), program 2 finishes 4 hours after that (C[2] = 6), and program 3 finishes 1 hour after that, so C[3] = 7. The latenesses are 0, 1, 0, and the maximum is 1, so the maximum lateness is 1.

In the same example, if you run programs 3 down to 1 in reverse order and designate program 3 to run in 1 hour, then program 3 starts now and finishes 1 hour later (C[3] = 1), program 2 finishes 4 hours after that (C[2] = 5), and program 1 finishes 2 hours after that, so C[1] = 7. The latenesses are 4, 0, 0, and the maximum is 4, so the maximum lateness is 4.

For this example, the first method minimizes the maximum lateness.

Given the running times and desired deadlines of N programs, find the minimum achievable maximum lateness.

Input

The first line gives the number of test cases T.

Each test case spans three lines. The first line gives the number of programs N.

The second line gives N integers separated by spaces, the running times H[i].

The third line gives N integers separated by spaces, the desired deadlines D[i].

Output

For each test case, print the minimum achievable maximum lateness.

Constraints

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 100,000
  • 1 ≤ H[i], D[i] ≤ 1,000

Examples1

  1. Example 1

    Input
    4
3
2 4 6
3 5 8
3
4 9 1
10 9 20
3
4 3 5
2 1 3
5
8 1 2 6 2
8 9 6 2 1
    Expected output
    1
0
5
5