레이팅 미적용Mirko drew a \(2 \times N\) by \(2 \times N\) chessboard and decided to play the following game:
On each square, he inscribed an integer denoting the value of that square. In the middle of the first
row (columns N and \(N+1\)), he placed two bishops. Mirko now calculates the lines of sight 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 instance, if N is 3, the squares within the line of sight of the two bishops (denoted by 'X') at their
starting positions (denoted by 'L') are as follows:
OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO
In a limited number of moves, Mirko tries to gain the maximum score by the following strategy:
1 Before making any moves, Mirko calculates the sum of the values on squares within the lines of sight
of the two bishops. That is Mirko's initial score.
2 On each turn, Mirko chooses one of the bishops and moves it to a square within its line of sight
3 On its new position, the bishop can now see new squares. The sum of those squares, previously
unseen by any of the bishops from the start of the game, is now added to Mirko's score.
Write a program which calculates the maximum score that Mirko can achieve in K turns.
INPUT DATA
The first line of input contains two integers N i K (\(1 \le N \le 10\), \(0 \le K \le 100\)), the dimension of the
chessboard and the number of turns.
The following \(2 \times N\) lines contain the values of the squares in the corresponding row, \(2 \times N\) values per
row. Those values are integers from ran\(ge -1\,000\,000\) to 1 000 000, inclusive.
OUTPUT DATA
In a single line of output, print the maximum score that Mirko can achieve.
\(8^{th}\) round, May \(14^{th}\), 2011
SCORING
In test cases worth a total of 40% points, K will be less or equal to 5.
EXAMPLE TEST DATA
2 0
\(0 -9 -9\ 0\)
0 1 1 0
1 0 0 1
0 0 6 0
4
input
2 1
\(0 -9 -9\ 0\)
0 1 1 0
1 0 0 1
0 0 6 0
output
1
2 0
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
4
2 1
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
1