Sane's Monthly Algorithms Challenge: October 2008

Cross Roads (Guru Level)

A flat rectangular grid of land separates four cities. Each city is situated on a different edge of the rectange

The four cities now wish to be joined by exactly 2 roads so that citizens may travel freely to and from each city. One road will join the North and South cities. Another road will join the West and East cities. The two roads will, of course, intersect somewhere, premitting anyone to travel to and from all four cities. Each road is a solid rectange of any width, with sides parallel to x and y axis.

The land separating the cities is a w x h grid of non-negative integers. Each value represents the cost of paving a road over the cell. To pave an entire road, all covered cells are paved and paid for exactly once. When paving the second road, the intersection does not need to be paved a second time.

If the roads are larger, more cars can travel from city to city. Therefore, you wish to maximize the total number of paved cells. However, you can not exceed the budget allocated for this job.

Determine the maximum number of cells which can be paved to build exactly 2 roads within the provided budget.

Input

The first line contains integers w, h (1 ≤ w, h ≤ 500) and budget (0 ≤ budget ≤ 2 000 000 000).

The next h lines contains w non-negative integers each ≤ 8000, representing the cost of paving a road over that cell.

Output

A single integer representing the largest possible area which can be paved with the given budget. If it is impossible to build both roads, output 0.

Sample Input 1

7 5 30

0 4 0 5 5 8 9

1 1 3 2 2 3 4

0 1 2 1 4 1 1

2 9 1 4 5 3 6

7 7 1 2 4 9 7

Sample Output 1

17

Sample Input 2

8 8 145

1 5 2 3 3 8 0 1

0 6 6 7 2 5 4 9

6 5 1 1 1 2 3 4

4 3 1 2 1 5 6 0

9 8 1 4 2 1 8 3

3 2 7 1 8 9 3 5

5 5 6 0 1 3 0 7

1 0 8 3 3 2 5 1

Sample Output 2

44

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Oct 26, 2008
Author: DrSane

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I wonder, does the name "Guru level" have anything to do with Guru, or your title of "Programming Guru"?

Kind of the second. I didn't title myself as "Programming Guru". The forum has a system that titles you as "Beginner" or "Hobbyist" or "Guru" etc... depending on your number of posts. Since I have been personally influenced by the forum, I decided the competition should be too. Guru is the highest rank, and so the hardest problem has that rank. 

I'll sleep better at night if I get no stupid solutions please. Fair submissions can easily solve this problem in under 1 second. Hacks and/or exploitations of any test data characteristics are completely unnecessary.