A Game of Tejas

0

0 votes
Problem

Tejas is bored after rocking the Commonwealth Chess Championship. So he makes a chessboard and decided to play the following game: The chessboard has 2*N rows and 2*N columns.

On each square, he writes an integer denoting the value of that square. In the middle of the first row (columns N and N+1), he places two bishops. Tejas now calculates the value along the lines of attack of the two bishops: these are squares on the same diagonal as one of the bishops, but not on the square covered by any of the bishops.

For example, if N is 2, the squares within the line of attack of the two bishops (denoted by 'X') at their starting positions (denoted by 'B') are as follows:

OBBO
XXXX
XOOX
OOOO

With a limited number of moves, Tejas tries to gain the maximum score by the following strategy:

  1. Before making any moves, Tejas calculates the sum of the values on squares within the lines of sight of the two bishops. That is Tejas’ initial score.
  2. Now, on each turn, Tejas chooses one of the bishops and moves it to a square within its line of attack.
  3. Now in its new position, the bishop may see some new squares. The sum of those squares, previously unseen by any of the bishops from the start of the game, is now added to Tejas’ score.


Find the maximum score that Tejas can achieve in M turns.

INPUT
The first line of input contains two integers N and M (1 ? N ? 10, 0 ? M ? 100).
The following 2×N lines contain the values of the squares in the corresponding row, 2×N values per row. Those values are integers from range -1 000 000 to 1 000 000, inclusive.

OUTPUT
In a single line of output, print the maximum score that Tejas can achieve.

Sample test case #1
Input
2 0
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
Output
4

Sample Test case #2
Input
2 1
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
Output
1

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?