Driving Exam

The driving licence exam in Byteotia takes place on a grid of streets. There are $n$ straight, parallel, one-way streets running north, meaning you may only drive from south to north on them. Each of these north-south streets is exactly $m$ meters long, and they all begin and end at the same latitude. They are numbered $1$ to $n$ from west to east.

There are also $p$ one-way horizontal streets, each perpendicular to the north-south streets. Every horizontal street connects a pair of adjacent north-south streets and is oriented either east or west. Where an east-oriented and a west-oriented horizontal street coincide, they form a two-way connection.

A sample testing area ($n=4$, $m=3$, $p=5$).

The examiner picks one north-south street as the start (the exam begins at its southern end) and another as the finish. The candidate must drive from the start to the finish while respecting every one-way direction.

The examiner may only start the exam on a street from which it is possible to reach the northern end of every north-south street. Call such a street a valid starting street.

There are usually only a few valid starting streets, which makes the examiners' work tedious. The board wants to build at most $k$ new horizontal streets (each oriented east or west and connecting a pair of adjacent north-south streets) so as to create as many new valid starting streets as possible. The original layout may or may not already contain valid starting streets.

Write a program that reads the layout and the number $k$, then outputs the largest number of new valid starting streets that can be created by building at most $k$ new horizontal streets.

The first line contains four integers $n$, $m$, $p$, and $k$ ($2 \le n \le 100000$, $1 \le m, k \le 100000$, $0 \le p \le 100000$): the number of north-south streets, their length, the number of existing horizontal streets, and the maximum number of new horizontal streets that may be built. The north-south streets are numbered $1$ to $n$ from west to east.

Each of the next $p$ lines contains three integers $n_i$, $m_i$, and $d_i$ ($1 \le n_i \le n-1$, $0 \le m_i \le m$, $d_i \in \{0, 1\}$) describing one horizontal street. It connects north-south streets $n_i$ and $n_i+1$, meeting each of them $m_i$ meters from its southern end. If $d_i = 0$ the street is oriented east (from street $n_i$ toward street $n_i+1$); if $d_i = 1$ it is oriented west (from street $n_i+1$ toward street $n_i$).

Print a single integer: the largest number of new valid starting streets that can be created by building at most $k$ new horizontal streets. A new horizontal street may meet the north-south streets at a non-integer distance from their southern end, and new horizontal streets may overlap to form two-way connections.

In the sample layout, the southern ends of streets $1$ and $3$ can be turned into valid starting streets, for example.