문제1171--KoreaTech 세계 일주를 꿈꾸다!

1171: KoreaTech 세계 일주를 꿈꾸다!

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

재우와 상엽이는 10월 11일자로 세계 여행을 떠나기로 했다. (이 둘은 4년간의 한기대 컴퓨터공학과 생활로 covid-19 따위는 감히 넘볼 수 없는 불사의 몸이 되었다.)
하지만 아무 생각이 없던 여행사 대표 종욱이는 각 나라별 주유량과 다음 나라에 도달하는데에 필요한 연료양을 세계 일주하는데에 필요한 만큼 지급해주는 나라들로만 이루어진 나라 리스트를 만들지 못했다.
따라서 재우와 상엽이는 나라 리스트를 일일이 비교하여 완주가 가능한 나라의 시작점을 선택해야만 한다. 단 이번 세계 여행 일주는 다음의 여행 규칙을 반드시 준수해야만 한다.

(단, 완주 자체가 불가능한 스케쥴이 있으므로 이점을 유의해야만 한다.)

<<여행 규칙>>

1. 반드시 여행은 시작과 끝나는 위치가 같은 나라여야만 한다. 

2. 여행은 리스트의 왼쪽에서 오른쪽 방향으로 떠난다.

- 단 마지막 위치에 있는 나라에 도달하면 그다음에는 다시 리스트의 처음 위치한 나라로 이동한다.

3. 시작할때 주유의 양은 0이며, 시작점에서 주유량 만큼 주유받고 시작을 한다.

- 단 비행기의 주유 가능량은 무한이라고 가정한다. (일명 슈퍼 비행기이다)

4. 주유량은 다음 목적지에 도달해도 보존된다, 단 연료량만큼 소비되고 남은 양만이 보존된다.

- 단 연료량을 차감하였을때, 음수가 되면 다음 나라로 갈 수 없다.

5. 어떠한 나라에서 시작을 하여도 완주를 못하는 경우도 있다.


재우와 상엽이가 세계 일주를 완주 할 수 있는 나라의 시작 위치는 어디이겠는가?

입력 설명

첫줄에는 전체 테스트 케이스 T(1<= T <= 10)가 주어지며 그다음 줄에서부터는 다음의 규칙으로 입력이 주어진다
각 테스트 케이스의 첫번째 나라의 수를 의미하는 C(1 <= C <= 355,000)가 주어진다.
그다음 줄에는 주유량 A를 이루는 숫자들이 C만큼 다음의 범위로(0 <= A[i] <= 1,000,000)  주어진다.
그다음 줄에는 다음 나라에 도착하는데 필요한 연료량 B를 이루는 숫자들이 C만큼 다음의 범위로(0 <= B[i] <= 1,000,000)  주어진다.

출력 설명

세계 일주가 가능한 나라 인덱스를 출력한다. 단 완주를 못할 경우 -1를 출력한다.(여러개의 나라가 가능할 경우, 그중에 인덱스가 가장 낮은 숫자를 출력해야만 한다.)

입력 예시 Copy

1
5
3 2 5 1 3
4 1 5 1 2

출력 예시 Copy

1

출처/분류