31461번 - 최고의 초콜릿 성지순례

문제

코코네 마을은 초콜릿 가게가 많이 있는 것으로 유명하다. 이 마을에는 1ドル\le x\le N,ドル 1ドル\le y\le 2$인 각 정수 $x,ドル $y$마다 좌표 $(x,y)$ 위치에 초콜릿 가게가 하나씩 있다. 이 중에는 코코와 한별이의 가게도 있으며, 코코의 가게는 $(a,b),ドル 한별이의 가게는 $(c,d)$에 있다. 코코네 마을의 도로는 조금 특이해서, $x$좌표의 차이와 $y$좌표의 차이가 모두 1ドル$ 이하인 모든 두 가게 사이에는 도로가 놓여 있어 한 가게에서 다른 가게로 이동할 수 있다.

아래 그림은 $N=5$이고 코코네 가게는 $(1, 1),ドル 한별이네 가게는 $(5, 2)$에 있는 경우의 예시이다.

코코는 한별이와 함께할 초콜릿 성지순례 코스를 계획하고 있다. 올바른 성지순례 코스는 다음과 같이 정의한다.

• 코코의 가게에서 시작해서 도로를 통해 이동하여 한별이의 가게에서 끝난다.
• 어떤 초콜릿 가게가 있는 곳에 도착하면 반드시 그 가게를 방문하며, 각 초콜릿 가게는 최대 한 번만 방문한다.

코코는 동네에 있는 모든 초콜릿 가게에서 파는 초콜릿의 맛을 점수로 매겨 놓았다. 성지순례 코스의 점수는 방문한 모든 초콜릿 가게에서 파는 초콜릿의 점수의 합이며, 코코와 한별이의 가게도 포함한다. 코코를 위해 최고의 성지순례 코스의 점수를 계산해 주자.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 1,円 000)$

각 테스트 케이스의 첫 번째 줄에는 정수 $N$의 값이 주어진다. $(1\le N\le 200,円 000)$

다음 두 줄에는 각 초콜릿 가게에서 파는 초콜릿의 점수가 주어진다. 좌표 $(x,y)$에 있는 초콜릿 가게의 점수를 $s_{(x,y)}$라고 할 때, 첫 번째 줄에는 $N$개의 정수 $s_{(1,1)},ドル $s_{(2,1)},ドル $\cdots,ドル $s_{(N,1)}$이, 두 번째 줄에는 $N$개의 정수 $s_{(1,2)},ドル $s_{(2,2)},ドル $\cdots,ドル $s_{(N,2)}$가 순서대로 공백으로 구분되어 주어진다. $(-1,円 000\le s_{(x,y)}\le 1,円 000)$

그다음 줄에는 코코의 가게와 한별이의 가게의 위치를 나타내는 $a,ドル $b,ドル $c,ドル $d$가 순서대로 공백으로 구분되어 주어진다. $(1\le a,c\le N;$ 1ドル\le b,d\le 2;$ $(a,b)\neq(c,d) )$

모든 테스트 케이스의 $N$의 합은 1ドル,円 000,円 000$을 초과하지 않는다.

출력

각 테스트 케이스에 대해, 가능한 모든 성지순례 코스 중에서 점수가 가장 높은 코스의 점수를 한 줄에 출력한다.

제한

힌트