A1434.[COCI-2010_2011-olympiad]#2 LOVCI

Mirko drew a 2×N by 2×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.

The first line of input contains two integers N i K (1 ≤ N ≤ 10, 0 ≤ K ≤ 100), the dimension of the chessboard and the number of turns.
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.

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

In test cases worth a total of 40% points, K will be less or equal to 5.