C. Christmas Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the center of a store, there is a Christmas tree represented as a cylinder. The development of the cylinder is a rectangle of size $$$N \times M$$$ cells. To decorate the tree, you can use $$$K$$$ types of ornaments. At most one ornament can be hung in each cell.

Any rectangular area of the tree of size $$$N \times W$$$ must contain at least $$$S$$$ ornaments to ensure the tree looks beautiful.

The cost of the $$$i$$$-th type of ornament is $$$P_i$$$ and it can be hung at a height of no more than $$$H_i$$$. What is the minimum cost of the set of ornaments required to decorate the tree?

Input

The first line contains five integers: the height of the development $$$N$$$, the width of the development $$$M$$$, the total number of types of ornaments $$$K$$$, the width of the section $$$W$$$, and the minimum number of ornaments $$$S$$$ required $$$(1 \leq N \leq 10^8, \, 1 \leq M \leq 10^8, \, N \cdot M \leq 10^8, \, 1 \leq W \leq M, \, 1 \leq K \leq 100,000, \, 1 \leq S \leq N \cdot W)$$$.

The next $$$K$$$ lines describe the ornaments. Each line contains three integers: price $$$P_i$$$, maximum height $$$H_i$$$, and quantity of ornaments $$$C_i$$$ for type $$$i$$$ $$$(1 \leq P_i \leq 100,000, \, 1 \leq C_i \leq 100,000, \, 1 \leq H_i \leq N)$$$.

Output

Output the minimum cost of the ornaments. If it is not possible to hang ornaments under the specified restrictions, output $$$-1$$$.

Examples
Input
5 4 4 2 3
2 3 3
1 1 3
3 5 2
1 5 2
Output
7
Input
6 2 1 2 4
2 2 20
Output
8
Input
6 2 1 2 5
2 2 20
Output
-1