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:
Cube evolvent
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 361Accepted: 100

Description

A square sheet of paper is partitioned into N*M equal squares by horizontal and vertical lines, 2 ≤ N ≤ 100, 2 ≤ M ≤ 100, N+M ≥ 7. A natural number not exceeding 20 000 is written in each square.

The task is to cut out a connected figure according to the following rules:

  •  you can cut only along the drawn lines;
  • the figure must contain exactly 6 squares;
  • the figure must a cube evolvent, i.e. it must be possible to obtain a cube model by folding the figure along the drawn lines;
  • the sum of the numbers on the evolvent must be the maximal possible.

Input

The first line contains two integers N and M separated by one or more spaces. The next N lines contain M integers each. The integers are separated by one or more spaces.

Output

This unique line contains the sum of the numbers on the found evolvent.

Sample Input

4 4
1 2 3 4
2 4 3 1
5 8 1 3
4 1 3 2

Sample Output

27

Source

Northeastern Europe 2003, Western Subregion

[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