题目描述

译自 POI 2007 Stage 3. Day 2「Egzamin na prawo jazdy」

Byteotian 驾驶考试所在的区域有 $n$ 条互相平行的自南向北的道路，每条道路长为 $m$ 米，且在同一条水平线上开始、结束。另有 $p$ 条自东向西或自西向东的道路，连接两条相邻的自南向北的道路。注意可能有两条自东向西的道路和自西向东的道路重合，相当于一条双向道路。

上图为 $n=4,m=3,p=5$ 的例子。

考生可以选择一条自南向北的道路作为起始点，且从该道路开始必须能到达其它所有的道路。

你需要添加至多 $k$ 条东西向的道路，使得满足条件的起始点最多。

输入格式

第一行四个整数 $n,m,p,k$（$2 \le n \le 100\ 000,1 \le m,k \le 100\ 000,0 \le p \le 100\ 000$），分别表示自南向北的道路数量、这些道路的长度、初始时已有的自东向西或自西向东的道路数量、可以添加的道路的数量。自南向北的道路从西向东编号为 $1 \ldots n$。

接下来 $p$ 行每行三个整数 $n_i, m_i, d_i (1 \le n_i \lt n,0 \le m_i \lt m,d_i \in \{0,1\})$，表示一条连接第 $n_i$ 和 $n_i+1$ 条自南向北的道路、且距离起点 $m_i$ 米的东西向道路。$d_i = 0$ 时为向东的道路，$d_i = 1$ 时为向西的道路。

输出格式

输出一行，表示新产生的起始点的最大数量。添加的东西向道路不一定要在整点和南北向道路相交。自东向西的道路和自西向东的可以重叠，相当于双向道路。

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

2