Bishop Doodle

Time limit1sMemory limit128 MB

Summary
Simulate two bishops on a 2N by 2N board moving K times to maximize the sum of newly-seen cells not previously visible to either bishop.
Level

Hard8 of 10

Topics
Dynamic programming, Simulation, Brute force, Implementation
Solved
No attempts yet

Problem

Sunyoung often doodles on paper while solving problems. Today she draws a 2N x 2N chessboard and plays the following game.

First, she writes one integer in each square. Initially, she places two bishops in the middle two squares of the first row, in columns N and N+1. A bishop's line of sight is every square it can move to diagonally from its current position; the square occupied by the bishop itself is not included.

When N = 3, the two bishops and their lines of sight look like this. L marks a bishop, X marks a square in sight, and O marks a square that is not in sight.

OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO

Sunyoung performs exactly K turns. The score is computed as follows.

  1. Before any bishop moves, the initial score is the sum of the numbers in all squares seen by the two bishops.
  2. On each turn, she chooses one bishop and moves it to one square that is currently in that bishop's line of sight.
  3. After the move, the bishop can see some squares from its new position. Add to the score the sum of the numbers in the squares that become visible now and have never been in either bishop's line of sight since the game began.

Find the maximum score she can obtain after all K turns.

Input

The first line contains two integers N and K. (1 <= N <= 10, 0 <= K <= 100)

Each of the next 2N lines contains 2N integers written in the corresponding row of the chessboard. Every integer is between -1,000,000 and 1,000,000, inclusive.

Output

Print the maximum score obtainable after exactly K turns.

Examples2

  1. Example 1

    Input
    2 0
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
    Expected output
    4

  2. Example 2

    Input
    2 1
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0
    Expected output
    1