Project Euler #149: Searching for a maximum-sum subsequence.

_{This problem is a programming version of Problem 149 from projecteuler.net}

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is ().

Now, let us repeat the search, but on a much larger scale.

First, generate pseudo-random numbers using the following generator:

The terms of are then arranged in a table, using the first numbers to fill the first row (sequentially), the next numbers to fill the second row, and so on.

For every from to , find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal), considering only the cells that belong to the first rows and columns.

Input Format

The input consists of exactly seven lines.

The st line of input contains , the dimension of the square grid.
The nd line contains a single integer .
The rd line contains integers separated by single spaces: .
The th line contains five integers and .
The th line contains a single integer .
The th line contains integers separated by single spaces: .
The th line contains five integers and .

Constraints

In input files #01-#10:
In input files #11-#20:

Output Format

Output lines. The th line must contain a single integer, denoting the greatest sum of (any number of) adjacent entries in any direction considering only the cells that belong to the first rows and columns.

Sample Input

8
4
81 -89 45 6
3 2 2 1 0
3
-78 -45 54
1 0 0 1 2

Sample Output

Explanation

The following is the whole grid:

As an example, the fifth answer is because the largest sum in the first five rows and columns is :

On the other hand, the sixth answer is because the largest sum in the first six rows and columns is :