## Topium

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Amy crashed onto a distant planet and broke her starship's window. Luckily, she explored the planet and discovered a new gem called Topium. Because of its many special properties, she wants to use it to create a new window.

Amy needs her ship to withstand the high temperature inside stars. After doing some experiments, she noticed that the gem consists of many small crystals arranged in a flat grid lattice with rows and columns. While most of these crystals are made of Topium, of them, called impurities, are made of other materials of varying strength. The melting point of any gem plate is equal to the sum of the strengths of all the impurities it contains. A plate containing no impurities (pure fragment) has a melting point of .

To create her window, Amy will need to cut out a rectangular plate with rows and columns. Help her determine the highest melting point of a plate she can use for her window.

#### Input Specification

The first line contains and .

The second line contains and .

The third line contains .

The next lines consist of integers , indicating an impurity at row and column with strength .

#### Output Specification

Output the maximum melting point of a rectangle with rows and columns that is contained in the gem.

#### Sample Input 1

1 1
5 5
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12

#### Sample Output 1

12

#### Explanation

The by rectangle with the highest melting point is .

#### Sample Input 2

2 2
10 10
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12

#### Sample Output 2

16

#### Sample Input 3

1 1
10 10
6
1 1 -10
2 2 -5
3 2 -8
2 3 -3
4 4 -1
5 5 -12

#### Sample Output 3

0