상점

면접 대비

시간 제한2초메모리 제한256 MB

요약

변을 공유하지 않도록 N행 5열 격자에서 칸을 골라 이익 합을 최대화합니다.

문제

N열 5행 격자의 각 칸에 예상 수익이 있다. 인접한 두 칸(상하좌우)을 동시에 임대할 수 없을 때, 임대 수익 합의 최댓값을 구하라.

첫 줄에 테스트 수 T. 각 테스트는 N, 이어서 5행의 N개 수익 값으로 주어진다.

각 테스트마다 인접 칸을 모두 피했을 때 얻을 수 있는 최대 총 수익을 출력한다.

예제 1

입력

2
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
6
1 0 0 0 0 0
0 1 1 10 1 0
1 10 0 0 5 10
0 1 1 10 0 0
1 0 0 0 1 10

예상 출력

13
52