동굴

동굴이 있는 땅을 가진 나는 지하 연료 탱크가 돈이 된다는 이야기를 듣고 반가웠다. 저장할 수 있는 부피가 클수록 좋다. 그런데 이 동굴은 모양이 꽤 복잡해서 실제로 쓸 수 있는 부피를 구하기가 쉽지 않다. 다행히 동굴은 한쪽 방향으로 납작해서 아래 그림처럼 단면 하나로 볼 수 있다.

동굴의 단면이다. 연료를 채울 수 있는 웅덩이를 검게 칠했다.

동굴 천장에는 전선이 지나간다. 절연이 멀쩡한지 확신할 수 없으니 연료 수면은 어느 지점에서나 천장보다 낮게 유지해야 한다. 연료는 동굴 안 원하는 자리에 원하는 만큼 부을 수 있고, 웅덩이를 여러 개 만들어도 된다. 다만 연료는 액체라서 위치 에너지가 가장 작은 상태로 놓인다. 평평한 바닥에서는 사방으로 고르게 퍼지고, 내려갈 곳이 있으면 흘러내리며, 서로 통하는 부분은 수면 높이가 같아진다. 동굴의 양 끝은 암반으로 막혀 있어서 연료가 밖으로 새지는 않는다.

동굴이 납작한 덕분에 수면과 천장 사이의 틈은 얼마든지 얇게 만들 수 있다. 위 규칙을 모두 지키면서 만들 수 있는 웅덩이 전체 넓이의 최댓값을 구하자.

첫 줄에 테스트 케이스의 개수 $Z$가 주어진다. ($1 \le Z \le 15$)

각 테스트 케이스의 첫 줄에는 동굴의 너비 $n$이 주어진다. ($1 \le n \le 10^6$)

둘째 줄에는 정수 $p_1, p_2, \dots, p_n$이, 셋째 줄에는 정수 $s_1, s_2, \dots, s_n$이 공백 하나로 구분되어 주어진다. $p_i$는 구간 $[i, i+1)$에서 바닥의 높이이고 $s_i$는 같은 구간에서 천장의 높이이며, $0 \le p_i < s_i \le 1000$이다.

각 테스트 케이스마다 동굴에 만들 수 있는 웅덩이 전체 넓이의 최댓값을 정수 하나로 한 줄에 출력한다.