[POI2007] EGZ-Driving Exam

The Byteotian driving licence exam takes place in an area in which there are $n$ straight, parallel, unidirectional, north-oriented streets (that is the allowed driving direction is south to north). Each of the streets is exactly $m$ meters long, all of them begin and end on the same level. These streets are numbered from $1$ to $n$ starting the westernmost. There are also $p$ unidirectional, east or west-oriented streets perpendicular to the abovementioned, each one of them connecting a pair of adjacent north-oriented streets. It is also possible that an east-oriented and a west-oriented street overlap, thus forming a bidirectional one.  An exemplary testing area ($n=4, m=3, p=5$). The examiner chooses a north-oriented street, at the beginnig of which the examination starts and anothernorth-oriented street, where it is to come to an end. The task of the applicant is to drive from the starting tothe final point, observing the allowed directions.The examiner always chooses as starting point a street, from which it is possible to drive to the endpointof any other north-oriented street.The work of the examiners is a very tedious one, because they always have to start at the beginning ofone of the few suitable streets. The board of directors have decided to build a new testing area on the basis ofpre-existent plans. It has been calculated, that available funds allow for no more than $k$ east or west-orientedstreets to be built. Those new streets are to be constructed in such a way, so as to add the largest possiblenumber of potential starting points (there may or may not exist starting points on the pre-existent plan). Newstreets have to connect pairs of adjacent north-oriented streets. ## Task Write a programme which: - reads a description of the testing area and the number $k$ from the standard input, - calculates the greatest number of potential new starting points for the examination, generated by adding no more than $k$ east or west-oriented streets, - writes the outcome to the standard output. 成都的驾驶考试在一个有n条平行的自南向北的单向的道路的场地中进行。每条道路长度为m米，并且都在同一条水平线上开始和结束。街道从西向东分别编号为1到n。同样有p条单向的自西向东或自东向西的街道垂直于上面描述的街道，每一条这样的街道链接了两个相邻的自南向北的道路。当然自西向东和自东向西的道路可以重叠，那就是一个双向的街道了。 考生选择一个自南向北的道路作为他考试的起始点和另外一个自南向北的道路作为他考试的终止点。他们的考试项目是将车从开始的道路驾驶到作为终止点的道路。考生们总是选择一个可以到达所有其他街道的起始道路作为开始点。现在，考生们总是感到十分无趣因为他们只有很少的起始道路可以选择，所以教练们决定改造先有的考试场所，由于经费的限制，他们决定添加至多K条东西向的道路，使得能够选择的起始道路尽量地多。

In the first line of the standard input there are four integers $n$, $m$, $p$ and $k$ ($2 \le n \le 100\ 000$, $1 \le m, k, \le 100\ 000$, $0 \le p \le 100\ 000$), separated by single spaces, denoting respectively: the number of north-oriented streets, the length of each one of them, the number of pre-existent east or west-oriented streets, the maximal number of new streets to be built. The north-oriented streets are numbered from $1$ to $n$, starting with the westernmost. The following $p$ lines contain three integers each: $n_i$, $m_i$ and $d_i$ ($1 \le n_i \le n$, $0 \le m_i \le m$, $d_i \in \{0, 1\}$), separated by single spaces, denoting the 'th east-oriented (for $d_i=0$) or west-oriented (for $d_i=1$) street. This street connects north-oriented streets $n$ and $n+1$, intersecting them in points $m_i$ meters distant from their beginning.

The first and only line of the standard output should contain a single integer, denoting the maximal numberof new examination starting points generated by building no more than $k$ east or west-oriented streets. Thenewly built streets **do not have to** intersect the north-oriented streets in points, whose distance from thebeginning of the street is an integer. The newly built east or west-oriented streets may overlap, thus formingbidirectional streets.

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

2