题目描述

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.

输入格式

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.

题目大意

题目描述

译自 POI 2007 Stage 3. Day 2「Egzamin na prawo jazdy」

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。

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

2