Domino in Casino

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Domino is well known as a game played by people at streets when they relax after a workday. So it was, until recently John Bigbuck introduced domino in his casino “BUMP ” (Bring Us Money, Please).
      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.

Input

      The first line of the input file contains integer numbers m, n and k (1 ≤ m ≤ 16, 1 ≤ n ≤ 100, 1 ≤ k ≤ 200). The following m lines contain n integer numbers each and describe board. Numbers written on the board are non-negative and do not exceed 1000. It is guaranteed that it is possible to arrange all tiles on a board.

Output

      Output one integer number — the maximal sum a player can get.

Sample Input

2 2 2
1 4
3 2

Sample Output

11

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number27
Submit Number82
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel