Shops

Interview

Time limit2sMemory limit256 MB

Summary

Pick cells with no shared side in an N by 5 profit grid to maximize the summed profit.

Level: Medium5 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

A fair site is an N by 5 grid. Each cell has a profit estimate. You may rent any set of cells, but no two rented cells may be side-adjacent (up, down, left, or right). Find the maximum total profit.

Input

The first line has T test cases. Each test case starts with N, followed by five lines of N nonnegative profits.

Output

For each test case, print the maximum total profit from a non-adjacent selection.

Examples4

Example 1

Input

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

Expected output

13
52

Example 2
Input
```
1
1
5
0
0
0
0
```
Expected output
```
5
```
Example 3
Input
```
1
2
10 0
0 10
0 0
0 0
0 0
```
Expected output
```
20
```
Example 4
Input
```
1
3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
```
Expected output
```
8
```