Byteotian 驾照考试在一个区域内进行，该区域有 $n$ 条笔直、平行且单向的北向街道（即允许的行驶方向为由南向北）。每条街道的长度均为 $m$ 米，且所有街道的起点和终点都在同一水平线上。这些街道从西向东依次编号为 $1$ 到 $n$。此外，还有 $p$ 条单向的东向或西向街道与上述街道垂直，每条街道连接一对相邻的北向街道。东向街道和西向街道也可能重叠，从而形成双向街道。

一个示例测试区域 ($n = 4, m = 3, p = 5$)

考官会选择一条北向街道作为考试的起点，并选择另一条北向街道作为终点。考生的任务是在遵守交通规则的前提下，从起点行驶到终点。

考官总是选择这样一条街道作为起点：从该街道的起点出发，能够行驶到任何其他北向街道的终点。

考官的工作非常繁琐，因为他们总是必须从少数几条合适的街道的起点开始考试。董事会决定在现有规划的基础上建设一个新的测试区域。据计算，现有资金允许新建不超过 $k$ 条东向或西向街道。这些新街道的建设目标是尽可能增加潜在的考试起点数量（现有规划中可能已经存在起点，也可能不存在）。新街道必须连接一对相邻的北向街道。

任务

编写一个程序，完成以下工作：

• 从标准输入读取测试区域的描述和数字 $k$。
• 计算通过新建不超过 $k$ 条东向或西向街道，所能产生的最大潜在考试起点数量。
• 将结果写入标准输出。

输入格式

第一行包含四个整数 $n, m, p$ 和 $k$ ($2 \le n \le 100000, 1 \le m, k \le 100000, 0 \le p \le 100000$)，用空格分隔，分别表示：北向街道的数量、每条街道的长度、现有东向或西向街道的数量，以及允许新建街道的最大数量。北向街道从 $1$ 到 $n$ 编号，从最西侧开始。

接下来的 $p$ 行，每行包含三个整数 $n_i, m_i$ 和 $d_i$ ($1 \le n_i < n, 0 \le m_i \le m, d_i \in \{0, 1\}$)，用空格分隔，表示第 $i$ 条东向（当 $d_i = 0$ 时）或西向（当 $d_i = 1$ 时）街道。该街道连接北向街道 $n_i$ 和 $n_i + 1$，并在距离它们起点 $m_i$ 米处相交。

输出格式

标准输出的第一行应包含一个整数，表示通过新建不超过 $k$ 条东向或西向街道所能产生的最大新考试起点数量。新建街道不必在距离街道起点整数米的位置与北向街道相交。新建的东向或西向街道可以重叠，从而形成双向街道。

样例

输入 1

4 3 5 2
2 0 0
2 2 1
3 3 1
1 1 1
3 3 0

输出 1

2

说明 1

例如，街道 1 和街道 3 的起点可以成为新的考试起点。