- All Contests
- ProjectEuler+
- Project Euler #149: Searching for a maximum-sum subsequence.

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

# 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**

```
-39
0
270
270
270
330
334
430
```

**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 :