스티커

상근이의 여동생 상냥이가 문방구에서 스티커를 $2n$장 샀다. 스티커는 2행 $n$열 격자로 붙어 있고, 상냥이는 이 스티커로 책상을 꾸미려고 한다.

스티커 품질이 나빠서 한 장을 떼면 그 스티커와 변을 맞대고 있는 스티커가 전부 찢어져 쓸 수 없게 된다. 즉 뗀 스티커의 위, 아래, 왼쪽, 오른쪽에 있는 스티커는 사용할 수 없다.

스티커를 전부 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 뗀 스티커의 점수 합이 가장 커지도록 고르기로 했다. $2n$장 가운데 서로 변을 맞대지 않는 스티커 집합을 골라 점수 합의 최댓값을 구하는 프로그램을 작성하시오.

점수가 가장 높은 두 스티커가 서로 변을 맞대고 있으면 둘을 함께 뗄 수 없다. 이럴 때는 점수가 낮더라도 서로 변을 맞대지 않는 조합을 찾아야 한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 $n$ ($1 \le n \le 100000$)이 주어진다. 이어지는 두 줄에는 각각 정수가 $n$개 주어지며, 각 정수는 그 자리에 있는 스티커의 점수이다. 연속한 두 정수는 공백 하나로 구분한다. 점수는 $0$ 이상 $100$ 이하의 정수이다.

각 테스트 케이스마다 서로 변을 맞대지 않게 고른 스티커 점수 합의 최댓값을 한 줄에 하나씩 출력한다.