Description

There are many settlements on Planet X. Pear decides to build a large water project to solve the water supply problem for the $N$ settlements under his control. There are now $N$ water towers and also $N$ settlements. The settlements are on the north side, numbered from $1$ to $N$ from west to east in a row; the water towers are on the south side, also numbered from $1$ to $N$ from west to east in a row.

There are $N$ vertical one-way water pipelines (powered by pumps) that carry water from the water towers on the south side to the corresponding settlements on the north side.

We may regard both settlements and water towers as points on a plane. The settlement coordinates are $(1,K) \sim (N,K)$, and the water towers are $(1,0) \sim (N,0)$.

In addition to the $N$ vertical pipelines, there are $M$ one-way horizontal pipelines, connecting $(X_i,Y_i)$ and $((X_i)+1,Y_i)$, or connecting $(X_i,Y_i)$ and $((X_i)-1,Y_i)$. The former is called a rightward waterway, and the latter is a leftward one. There will not be two waterways overlapping, even if they have different directions.

A schematic of the layout is shown in the figure.

Obviously, the water from each water tower can reach several settlements (not just the corresponding one). For example, in the figure above, water tower $4$ can reach settlements $3$, $4$, $5$, and $6$.

Now Pear decides to build one more horizontal one-way pipeline on top of this layout. For convenience, Pear requires this waterway to go from left to right, that is, it connects a point and the point immediately to its right (for example, the horizontal waterway in the figure that connects the two vertical lines $5$ and $6$).

Pear’s goal is that, after building this waterway, as many pairs of water towers and settlements as possible become reachable. In other words, suppose that after construction, the $i$-th water tower can reach $A_i$ settlements; you need to maximize $A_1+A_2+ \cdots +A_n$.

By definition, this new waterway must be parallel to the $x$-axis, but its $y$-coordinate does not have to be an integer. Note that although the input has no overlapping waterways, your plan may let the newly built pipeline overlap with existing waterways.

Input Format

The first line contains three positive integers $N$, $M$, $K$, as described in the statement: $N$ is the number of vertical lines, $M$ is the number of horizontal lines, and $K$ is the $y$-coordinate of the settlements.

The next $M$ lines each contain three integers. The first two positive integers $X_i,Y_i$ indicate the starting coordinate of a waterway;

$1 \le X_i \le N,0<Y_i<K$.

Then there is a number $0$ or $1$. If it is $0$, the waterway goes left; otherwise, it goes right.

It is guaranteed that all waterways are valid, meaning they will not flow to an undefined location.

Output Format

Output one line containing a positive integer, which is the maximum value of $A_1+A_2+ \cdots +A_n$ required by the problem.

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

11

7 9 4
2 3 0
7 2 0
6 3 1
6 1 0
2 1 1
3 3 1
5 2 0
2 2 1
7 1 0

21

Hint

For $20\%$ of the testdata, $N,K \le 20$, $M \le 100$.

For $40\%$ of the testdata, $N,K \le 100$, $M \le 1000$.

For $60\%$ of the testdata, $N,K \le 1000$, $M \le 100000$.

For $100\%$ of the testdata, $N,K \le 50000$, $M \le 10^5$.

Time limit: 4 seconds, 256 MB. Lanqiao Cup 2014, the 5th National Contest.

Translated by ChatGPT 5