상근이의 여동생 상냥이는 문방구에서 스티커 \(2n\)개를 구매했다. 스티커는 2행 \(n\)열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.

즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.

각 스티커의 점수가 주어졌을 때, 상냥이가 뗄 수 있는 스티커 점수의 최댓값을 구하는 프로그램을 작성하시오.

즉, \(2n\)개의 스티커 중에서 서로 변을 공유하지 않는 스티커 집합의 점수 합을 최대화해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.

각 테스트 케이스의 첫째 줄에는 \(n\) (\(1 \le n \le 100000\))이 주어진다.

다음 두 줄에는 각각 \(n\)개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다.

점수는 \(0\) 이상 \(100\) 이하의 정수이다.

출력

각 테스트 케이스마다 뗄 수 있는 스티커 점수의 최댓값을 한 줄에 하나씩 출력한다.

제한사항

• \(1 \le n \le 100000\)
• 각 스티커 점수: \(0 \le \text{score} \le 100\)

예제 입력 1

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력 1

260
290

출처

ACM-ICPC Asia Regional 2013