#P3463. [POI 2007] EGZ-Driving Exam

[POI 2007] EGZ-Driving Exam

题目描述

The Byteotian driving licence exam takes place in an area in which there are nn straight, parallel, unidirectional, north-oriented streets (that is the allowed driving direction is south to north). Each of the streets is exactly mm meters long, all of them begin and end on the same level. These streets are numbered from 11 to nn starting the westernmost. There are also pp 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=5n=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 kk 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 kk from the standard input,

  • calculates the greatest number of potential new starting points for the examination, generated by adding no more than kk east or west-oriented streets,

  • writes the outcome to the standard output.

输入格式

In the first line of the standard input there are four integers nn, mm, pp and kk (2n100 0002 \le n \le 100\ 000, 1m,k,100 0001 \le m, k, \le 100\ 000, 0p100 0000 \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 11 to nn, starting with the westernmost.

The following pp lines contain three integers each: nin_i, mim_i and did_i (1nin1 \le n_i \le n, 0mim0 \le m_i \le m, di{0,1}d_i \in \{0, 1\}), separated by single spaces, denoting the 'th east-oriented (for di=0d_i=0) or west-oriented (for di=1d_i=1) street. This street connects north-oriented streets nn and n+1n+1, intersecting them in points mim_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 kk 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