H. Enchanted
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amy crashed onto a distant planet and broke her starship's window. She needs to replace it with resources from the planet.

After some exploration, Amy found a gem consisting of many small crystals arranged in a flat grid lattice with $$$N$$$ rows and $$$M$$$ columns. While most of these crystals are identical, $$$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$$$.

Any ship must be heat resistant so it can withstand the high temperature inside stars. 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 new window.

Input

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$$$.

## Constraints

$$$1 \le x, R \le N \le 10^9$$$

$$$1 \le y, C \le M \le 10^9$$$

$$$1 \le K \le 10^5$$$

$$$-10^{12} \le t \le 10^{12}$$$

### Subtask 1 [10 $$$1 \le N, M \le 1\,000$$$

Output

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

Examples
Input
1 1
10 10
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12
Output
12
Input
2 2
10 10
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12
Output
16
Input
1 1
10 10
6
1 1 -10
2 2 -5
3 2 -8
2 3 -3
4 4 -1
5 5 -12
Output
0
Input
3 3
5 5
5
3 3 1000
1 3 -9999
5 3 -9999
3 1 -9999
3 5 -9999
Output
1000
Note

First sample:

The $$$1$$$ by $$$1$$$ rectangle with the highest melting point is $$$(5,5)$$$.