Codeforces Round 829 (Div. 1) |
---|

Finished |

brute force

two pointers

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Minecraft Series

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputLittle Misha goes to the programming club and solves nothing there. It may seem strange, but when you find out that Misha is filming a Minecraft series, everything will fall into place...

Misha is inspired by Manhattan, so he built a city in Minecraft that can be imagined as a table of size $$$n \times m$$$. $$$k$$$ students live in a city, the $$$i$$$-th student lives in the house, located at the intersection of the $$$x_i$$$-th row and the $$$y_i$$$-th column. Also, each student has a degree of his aggressiveness $$$w_i$$$. Since the city turned out to be very large, Misha decided to territorially limit the actions of his series to some square $$$s$$$, which sides are parallel to the coordinate axes. The length of the side of the square should be an integer from $$$1$$$ to $$$\min(n, m)$$$ cells.

According to the plot, the main hero will come to the city and accidentally fall into the square $$$s$$$. Possessing a unique degree of aggressiveness $$$0$$$, he will be able to show his leadership qualities and assemble a team of calm, moderate and aggressive students.

In order for the assembled team to be versatile and close-knit, degrees of aggressiveness of all students of the team must be pairwise distinct and must form a single segment of consecutive integers. Formally, if there exist students with degrees of aggressiveness $$$l, l+1, \ldots, -1, 1, \ldots, r-1, r$$$ inside the square $$$s$$$, where $$$l \le 0 \le r$$$, the main hero will be able to form a team of $$$r-l+1$$$ people (of course, he is included in this team).

Notice, that it is not required to take all students from square $$$s$$$ to the team.

Misha thinks that the team should consist of at least $$$t$$$ people. That is why he is interested, how many squares are there in the table in which the main hero will be able to form a team of at least $$$t$$$ people. Help him to calculate this.

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$ and $$$t$$$ ($$$1 \le n, m \le 40\,000$$$, $$$1 \le n \cdot m \le 40\,000$$$, $$$1 \le k \le 10^6$$$, $$$1 \le t \le k + 1$$$) — the number of rows and columns in the table, and the number of students living in the city, respectively.

Each of the following $$$k$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le \lvert w_i \rvert \le 10^9$$$) — the number of row and column, where the $$$i$$$-th student is living, and the degree of his aggressiveness.

Output

Print one integer — the number of ways to choose the square $$$s$$$ in such way that the main hero will be able to form a team of at least $$$t$$$ people.

Examples

Input

2 2 1 2 1 1 2

Output

0

Input

2 2 2 2 1 1 1 2 2 2

Output

2

Input

2 2 4 2 1 1 1 1 1 -1 1 2 1 2 2 1

Output

4

Note

- In the first example the main hero will not be able to form a team of more than one person in any square $$$s$$$.
Illustration for the first example. - In the second example there are two ways to select square $$$s$$$. Both of them are illustrated below. In one of them the main hero will be able to form a team of students with degrees of aggressiveness $$$[0, 1]$$$, and in the another — with degrees of aggressiveness $$$[0, 1, 2]$$$. Notice, that the main hero with degree of aggressiveness $$$0$$$ will be included to the team regardless of the chosen square.
Illustration for the second example. - In the third example there are four ways to select square $$$s$$$. All of them are illustrated below. The main hero will be able to form a team with degrees of aggressiveness: $$$[-1,0,1]$$$, $$$[0,1]$$$, $$$[0,1]$$$, $$$[-1, 0, 1]$$$, respectively.
Illustration for the third example.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 22:37:46 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|