Enchanted
Description
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.
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 the maximum melting point of a rectangle with $R$ rows and $C$ columns that is contained in the gem.
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.
1 1
10 10
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12
2 2
10 10
6
1 1 10
2 2 5
3 2 8
2 3 3
4 4 -1
5 5 12
1 1
10 10
6
1 1 -10
2 2 -5
3 2 -8
2 3 -3
4 4 -1
5 5 -12
3 3
5 5
5
3 3 1000
1 3 -9999
5 3 -9999
3 1 -9999
3 5 -9999
12
16
0
1000
Note
First sample:
The $1$ by $1$ rectangle with the highest melting point is $(5,5)$.