题目描述

成都的驾驶考试在一个有 $n$ 条平行的自南向北的单向的道路的场地中进行。每条道路长度为 $m$ 米，并且都在同一条水平线上开始和结束。街道从西向东分别编号为 $1$ 到 $n$。同样有 $p$ 条单向的自西向东或自东向西，宽度为 $1$ 米的街道于单向垂直于上面描述的街道，每一条这样的东西或者西东方向街道单向连接了两个相邻的自南向北的道路。（意思是，假设在第 $i$ 条从南向北的道路的第 $x$ 米处有一条单向连接到在 $i$ 西边的第 $i-1$ 条道路，那么在第 $i$ 条道路上行驶至第 $x$ 米时就可以向西拐弯前往第 $i-1$ 条道路的第 $x$ 米处）当然，自西向东和自东向西的道路可以重叠，那就是一个双向的街道了。

考生选择一个自南向北的道路作为他考试的起始点和另外一个自南向北的道路作为他考试的终止点。他们的考试项目是将车从开始的道路驾驶到作为终止点的道路。考生们总是选择一个可以到达所有其他街道的起始道路作为开始点。现在，考生们总是感到十分无趣因为他们只有很少的起始道路可以选择，所以教练们决定改造现有的考试场所，由于经费的限制，他们决定添加至多 $k$ 条东西单向的道路，使得能够选择的起始道路尽量多。

输入格式

输入第一行包含四个整数 $n,m,p,k$ $(2\leq n\leq 10^5,0\leq p\leq 10^5,1\leq m,k \leq 10^5)$。分别表示南北向的道路数，南北向道路的长度，东西向的道路数和最多能够添加的道路数。

接下来 $p$ 行，每行包含三个整数 $n_i,m_i,d_i$ $(1\leq n_i < n，0 \leq m_i < m，d_i = \{0, 1\})$，表示一条自西向东 $(d_i=0)$ 或者自东向西 $(d_i=1)$ 的道路。这个道路连接了南北向的道路 $n_i$ 和 $n_i+1$，在第 $m_i$ 米的地方进行了连接。

输出格式

输出中仅包含一个整数，最大的新增的能够作为起点的道路数（不包括原来就能作为起点的道路数）。注意添加的道路不能与南北向的道路相交（只能连接相邻的），并且到起始水平线的距离为整数。添加的道路可以重叠，表示双向的道路。

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

2

数据规模与约定

$2\leq n\leq 10^5,0\leq p\leq 10^5,1\leq m,k \leq 10^5$

题目来源

[POI2007] 驾驶考试egz