题目描述

经过数月的蒙古人袭击，中国帝国终于将他们赶出国土，但长城已经残破不堪。中国人不想把它完全推倒重建，而是决定只修复缺失的部分。

最初，城墙由 $S$ 个连续区段组成，编号为 $1$ 到 $S$。每个区段长度为 $1$ 米，高度为 $H$ 米。

之后发生了 $N$ 次袭击。第 $i$ 次袭击会作用于连续区间 $[L_i,R_i]$，并使这些区段的高度减少 $T_i$ 米。如果某些区段当前高度小于 $T_i$，则这些区段会被完全摧毁，高度变为 $0$。

现在准备了一批石块，每块石块长度为 $K$ 米，高度为 $1$ 米。石块水平放置，长边与城墙方向平行，短边与相邻石块接触。如果需要，可以把某些石块截短以适应更短的空缺，但截下来的剩余部分会被丢弃，不能用于其他地方。

你的任务是计算：为了把城墙恢复到最初的形状，最少需要多少块石块。

输入格式

第一行输入四个正整数 $N,S,H,K$，分别表示袭击次数、城墙初始长度、初始高度、石块长度。

接下来 $N$ 行，每行输入三个正整数 $L_i,R_i,T_i$，表示第 $i$ 次袭击影响的区间以及削去的高度。

输出格式

输出一行一个整数，表示最少需要的石块数量。

数据范围

• $1\le N\le 10^5$
• $1\le S,H,K\le 10^8$
• $1\le L_i\le R_i\le S$
• $1\le T_i\le 10^8$

子任务

只有通过某个子任务的全部测试，才能获得该子任务分数。

样例

输入

7 10 5 2
2 4 3
6 7 4
4 6 3
8 10 2
9 10 1
10 10 1
1 2 1

输出

20

解释

袭击结束后，城墙会形成若干缺口。每块石块高度为 $1$，长度最多为 $K=2$，可以截短但不能拼接剩余部分。按层修复每一段连续缺口，可得到最少需要 $20$ 块石块。