Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Chessboard Puzzle
Time Limit: 2000MSMemory Limit: 131072K
Total Submissions: 588Accepted: 280

Description

Farmer John has invented a game, Chessboard Puzzle, which perplexes lots of puzzle fanatics. The game is quite simple. Given a chessboard in such a way that every grid is presented by a specified integer, you are obliged to color every grid in white or black. For each pair of grids subjected to following restraints:

  1. they are neighbor, in detail, sharing common edge;
  2. they are colored differently.

add the product of the two specified integers to the score. And your goal is to maximum the total score. Could you write a program to tell John the maximum score?

Input

The input describes one puzzle which begins with two integer n, m(1 ≤ n, m ≤16). Then n lines follow. Each contains m integers. The j-th number on i-th row corresponds to the grid(i,j). The absolute value of each number is less than 1000.

Output

Print the maximum score in a line.  

Sample Input

5 5
-136 -712 -286 -622 564 
6 -899 623 -152 -519 
904 982 593 799 93 
-815 122 -307 572 -359 
921 757 -888 351 935

Sample Output

5852863

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator