Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 N rows and M columns. While most of these crystals are made of Topium, K 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 0.

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

Input Specification

The first line contains R and C.

The second line contains N and M.

The third line contains K.

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

Output Specification

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

Constraints

1\le x,R\le N\le10^9
1\le y,C\le M\le10^9
1\le K\le10^5
-10^{12}\le t\le10^{12}

Subtask 1 [10%]

1\le N,M\le1\,000

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 1 by 1 rectangle with the highest melting point is (5,5).

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

Comments

There are no comments at the moment.