Of course, ordinary domino games are not well suited for casino, so John had to introduce his own game. The game is played on a rectangular board of size m × n. Each cell of the board contains some integer number.
The player has k domino tiles — rectangles 2 × 1. The player puts the tiles to the board without overlapping and his winning is calculated as the sum of products of numbers under each tile.
For example, there are 2 ways to put 2 tiles on a 2 × 2 board. For the board below, the better way to put the tiles is shown on the left — in this case the sum is 1 × 3 + 4 × 2 = 11. If the player puts tiles to the board as shown on the right picture, the sum would be 1 × 4 + 3 × 2 = 10, which is smaller.
Given the board, and the number of the tiles the player has, find what is the maximal sum he can get.
2 2 2 1 4 3 2