P3463 [POI 2007] EGZ-Driving Exam

**译自 POI 2007 Stage 3. Day 2「[Egzamin na prawo jazdy](https://szkopul.edu.pl/problemset/problem/nLSrpyeJ1JnFGbBORYVVavIQ/site/?key=statement)」** 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$ 时为向西的道路。

输出一行，表示**新产生**的起始点的最大数量。添加的东西向道路**不一定**要在整点和南北向道路相交。自东向西的道路和自西向东的可以重叠，相当于双向道路。 翻译来自于 [LibreOJ](https://loj.ac/p/2661)。