DMOPC '15 Contest 1 P5 - Lelei and Dragon Scales

View as PDF

Points: 10 (partial)
Time limit: 0.5s
Memory limit: 128M

Author:
Problem types

Lelei is surveying a large field made up of cells.

A large battle involving dragons has taken place here, and as such there are scales from dragons strewn all about the field. As dragon scales are extremely valuable and fetch a high price, Lelei would like to collect as many as possible. However, a battlefield is a pretty dangerous place to be, so she can only risk spending enough time on it to pick up the scales in a rectangular subsection of the field with a total area up to .

Given the distribution of scales on the field and the maximum that Lelei has time for, can you help her determine how many scales she'll end up with if she chooses an optimal section of the field?

Input Specification

The first line of input will contain 3 space-separated integers , , and .
The next lines of input will each contain space-separated integers in the range .

Output Specification

A single integer, the maximum number of scales that Lelei can pick up.

Sample Input 1

5 5 4
0 0 0 0 10
0 5 0 1 2
2 0 3 7 1
8 9 0 1 3
1 5 2 3 7

Sample Output 1

23

Explanation for Sample Output 1

Lelei should explore the bottom-left corner of the field, which would allow her to collect scales.

Sample Input 2

1 2 1
0
5

Sample Output 2

5

Explanation for Sample Output 2

Lelei only has time for cell, so she should choose the one with scales.