CF1753F Minecraft Series

## 题意翻译 小 Misha 参加了编程社，但是一道题也没有做出来。这件事看上去有些匪夷所思，但你发现 Misha 正在摄制一部《我的世界》剧集时，一切就都说得通了。 Misha 受到曼哈顿地区道路的启发，在《我的世界》里建造了一座城市，其可以视为一个 $n \times m$ 的表格。城里住着 $k$ 名学生，其中第 $i$ 名学生住在第 $x_i$ 行和第 $y_i$ 列的交叉处，每名学生都有一个易怒值 $w_i$。由于城市的规模很大，Misha 决定将剧集的故事情节限制在发生于某个正方形区域 $s$ 中，其各边均与坐标轴平行。正方形区域的边长应当是一个 $\geqslant 1$ 且 $\leqslant \min(n, m)$ 的整数。 根据情节，主角将会来到这座城市并意外进入正方形区域 $s$ 里。主角的易怒值为 $0$，所以他可以利用自己的领导才能召集一个由平静、不温不火和易怒的学生们组成的团队。 为了使团队有机动性并团结紧密，团队中所有学生的易怒值必须各不相同且必须能够组成一条连续的序列。形式上说，如果存在有学生的易怒值可以组成一条形如 $ l, l+1, \ldots, -1, 1, \ldots, r-1, r $ 的序列，其中 $ l \le 0 \le r $，那么主角就能召集一个由 $r - l + 1$ 人组成的团队（主角自己也在团队中）。 请注意，不一定要把正方形区域 $s$ 内的所有学生都加入团队。 Misha 觉得这个团队至少应该容纳 $t$ 人。他很想知道：这个表格里有多少个正方形区域可供主角召集一个团队？请帮他算一算。

第一行分别是四个整数 $n$、$m$、$k$ 和 $t$（$ 1 \leqslant n, m \leqslant 40\,000 $，$ 1 \leqslant n \cdot m \leqslant 40\, 000 $，$ 1 \leqslant k \leqslant 10^6 $，$ 1 \leqslant t \leqslant k + 1 $），分别代表表格里的行数、列数，城市里学生的总数和一个团队的人数下限。 接下来的 $k$ 行，每行有三个整数 $x_i$、$y_i$ 和 $w_i$（$ 1 \leqslant x_i \leqslant n $，$ 1 \leqslant y_i \leqslant m $，$ 1 \leqslant \lvert w_i \rvert \leqslant 10^9 $），分别代表第 $i$ 名学生居住在的行数、列数以及他的易怒值。

一行一个整数，表格里可供主角召集一个团队的正方形区域的总数。

1. 在样例一中，如图，主角无法在任何正方形区域 $s$ 中召集到至少包含 $2$ 人的团队。 2. 在样例二中，如图，主角有两种召集团队的方式： 1. 成员易怒值分别为 $\left [0, 1 \right ]$； 2. 成员易怒值分别为 $\left [ 0, 1, 2 \right ]$。 注意，无论哪种方式，主角的易怒值 $0$ 都会被包含在团队中。 3. 在样例三中，如图，主角有四种召集团队的方式： 1. 成员易怒值分别为 $\left [-1, 0, 1 \right ]$； 2. 成员易怒值分别为 $\left [0, 1 \right ]$； 3. 成员易怒值分别为 $\left [0, 1 \right ]$； 4. 成员易怒值分别为 $\left [-1, 0, 1 \right ]$。