슈퍼 컴퓨터

당신은 슈퍼 컴퓨터에서 총 N개의 프로그램을 순차적으로 실행하여 실험을 해야한다.

편의상 프로그램은 1번부터 N번까지 번호가 매겨져 있으며 i번 프로그램은 총 H[i]시간 동안 실행되며 이 프로그램의 희망 데드라인은 지금부터 D[i]시간 후다.

N개의 프로그램이 있으므로 실행하는 순서는 총 N! 가지가 가능하다.

i번 프로그램이 끝나는 시각을 지금부터 C[i] 시간 후 라고 하자. 편의상 max(0, C[i] - D[i]) 를 i번 프로그램의 "지각도" 라고 칭하자 (희망 데드라인보다 늦게 끝나지 않은 경우엔 지각도가 0이다).

"최대 지각도"는 N개 프로그램의 지각도 중 최대값으로 정의한다.

그런데 이 슈퍼 컴퓨터에는 특이한 기능이 있는데, N개의 프로그램 중 딱 하나의 프로그램을 (당신이) "최우선 처리 대상"으로 지정하여 해당 프로그램은 무조건 1시간만에 실행되도록 할 수 있다.

예를 들어 N = 3, H = [2, 4, 6], D = [3, 5, 8]이라 하자.

이 경우, 1번부터 3번 프로그램까지 순서대로 실행을 하고 3번 프로그램 실행시간을 1시간이 되도록 지정했다면,

1번 프로그램은 지금부터 시작하여 2시간 후에 끝나며 (C[1] = 2), 2번은 그로부터 4시간 후에 끝나고 (C[2] = 6), 3번은 그로부터 1시간 후에 끝나서 C[3] = 7이 된다.

이 때 각 프로그램의 지각도는 0, 1, 0이며, 이 중 최대값이 1이므로 최대 지각도는 1이다.

같은 예제에서 3번 프로그램부터 1번 프로그램까지 역순으로 실행하고, 3번 프로그램의 실행시간을 1시간이 되도록 지정했다면,

3번 프로그램은 지금부터 시작하여 1시간 후에 끝나며 (C[3] = 1), 2번은 그로부터 4시간 후 (C[2] = 5), 1번은 그로부터 2시간 후에 끝나서 C[1] = 7이 된다.

이 때 각 프로그램의 지각도는 4, 0, 0이며, 이 중 최대값이 4이므로 최대 지각도는 4이다.

이 예제의 경우, 첫 번째 방법이 최대 지각도를 최소화 하는 방법이다.

입력으로 N개의 프로그램의 실행시간과 희망 데드라인이 주어졌을 때, 달성 가능한 최대 지각도의 최소값을 구하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스크 케이스는 세 줄에 걸쳐 주어지는데, 그 중 첫 줄에 프로그램의 수 N이 주어진다.

둘째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 실행시간 H[i]를 나타낸다.

셋째 줄에 N개의 정수가 공백으로 구분되어 주어지며, 희망 데드라인 D[i]를 나타낸다.

각 테스트 케이스에 대해 달성 가능한 최대 지각도의 최소값을 출력한다.