운전면허 시험

바이트오티아의 운전면허 시험은 격자 모양의 도로망에서 치러진다. 남북 방향으로 뻗은 일방통행 도로가 $n$개 있으며, 이 도로에서는 남쪽에서 북쪽으로만 달릴 수 있다. 각 남북 도로의 길이는 정확히 $m$미터이고, 모두 같은 위도에서 시작해 같은 위도에서 끝난다. 도로는 서쪽부터 동쪽으로 $1$번부터 $n$번까지 번호가 매겨져 있다.

또한 남북 도로에 수직인 일방통행 가로 도로가 $p$개 있다. 각 가로 도로는 인접한 두 남북 도로를 잇고, 동쪽 또는 서쪽을 향한다. 동쪽으로 향하는 가로 도로와 서쪽으로 향하는 가로 도로가 같은 위치에 겹치면 양방향 도로가 된다.

예시 도로망 ($n=4$, $m=3$, $p=5$).

시험관은 남북 도로 하나를 출발지로(시험은 그 도로의 남쪽 끝에서 시작한다), 다른 하나를 도착지로 고른다. 응시자는 모든 일방통행 방향을 지키면서 출발지에서 도착지까지 운전해야 한다.

시험관은 그 남쪽 끝에서 출발하여 모든 남북 도로의 북쪽 끝에 도달할 수 있는 도로만 출발지로 고를 수 있다. 이런 도로를 유효한 출발 도로라고 하자.

유효한 출발 도로는 보통 몇 개 없어서 시험관의 업무가 번거롭다. 이사회는 새 가로 도로를 최대 $k$개까지(각각 동쪽 또는 서쪽을 향하며 인접한 두 남북 도로를 잇는다) 건설하여, 새로 생기는 유효한 출발 도로의 수를 최대한 늘리려고 한다. 원래 도로망에 유효한 출발 도로가 이미 있을 수도, 없을 수도 있다.

도로망과 수 $k$를 입력받아, 최대 $k$개의 새 가로 도로를 건설하여 새로 만들 수 있는 유효한 출발 도로 수의 최댓값을 출력하는 프로그램을 작성하라.

첫 줄에 네 정수 $n$, $m$, $p$, $k$가 주어진다 ($2 \le n \le 100000$, $1 \le m, k \le 100000$, $0 \le p \le 100000$). 각각 남북 도로의 수, 그 길이, 기존 가로 도로의 수, 새로 건설할 수 있는 가로 도로의 최대 개수를 뜻한다. 남북 도로는 서쪽부터 $1$번부터 $n$번까지 번호가 매겨진다.

이어지는 $p$개의 줄에는 각각 세 정수 $n_i$, $m_i$, $d_i$가 주어진다 ($1 \le n_i \le n-1$, $0 \le m_i \le m$, $d_i \in \{0, 1\}$). 이 가로 도로는 남북 도로 $n_i$번과 $n_i+1$번을 잇고, 두 도로의 남쪽 끝에서 각각 $m_i$미터 떨어진 지점에서 만난다. $d_i = 0$이면 동쪽 방향($n_i$번에서 $n_i+1$번으로), $d_i = 1$이면 서쪽 방향($n_i+1$번에서 $n_i$번으로)이다.

정수 하나를 출력한다: 최대 $k$개의 새 가로 도로를 건설하여 새로 만들 수 있는 유효한 출발 도로 수의 최댓값. 새 가로 도로는 남북 도로의 남쪽 끝에서 정수가 아닌 거리에서 만나도 되며, 새 가로 도로끼리 겹쳐 양방향 도로를 이룰 수도 있다.

예시 도로망에서는 예를 들어 $1$번과 $3$번 도로의 남쪽 끝을 유효한 출발 도로로 만들 수 있다.