Treasure of the Alpaca King

Problem Source

SDOI2010

Problem Description

In the vast African desert lives a diligent and brave family of alpacas. Their leader, respectfully called "the Prophet" by his people, is Alpaca L. Sotomon; outsiders also call him "the Alpaca King". The Alpaca King devoted his life to maintaining the stability and harmony of his family, and once personally led his army to crush the barbaric invasion of the River-Crab Empire, winning great military glory for his people. The Alpaca King amassed countless treasures in his life, but being frugal and modest by nature, he buried them in an underground palace of his own design — which is also where Henry Curtis's story begins today. Henry is a greedy fellow who loves money as his own life, yet is also very clever; he schemed this theft meticulously, cracked layers of traps, and now stands before the underground palace.

The whole palace is laid out as a matrix, consisting of $R \times C$ rectangular chambers. Among them, $N$ chambers hide treasures and are called treasure chambers. Between chambers, both inside and outside the palace, stand solid walls; one can only move from one chamber to another through the unique moving method invented by the Alpaca King — teleportation gates. The Alpaca King built one teleportation gate for each of the $N$ treasure chambers; chambers without treasure have no gate. All chamber gates come in three types:

• "Horizontal Gate": from this gate you can teleport to any chamber in the same row.
• "Vertical Gate": from this gate you can teleport to any chamber in the same column.
• "Any Gate": from this gate you can teleport to any of the 8 surrounding chambers centred at this one (if the target chamber exists).

The far-sighted Henry of course obtained the Alpaca King's palace tender document in advance, which records in detail each gate's chamber and type. Moreover, although the palace is sealed off from the outside, he prepared his own portable teleportation gate, which can send him to any chamber inside to begin the treasure hunt, and out from any chamber to end it. The whole palace may be entered and exited only once, and the portable gate cannot teleport between chambers. Fortunately, the gates inside the chambers can be used without limit, and each chamber may be visited multiple times.

Now Henry has opened his portable gate and is about to choose a chamber to enter. To obtain as much treasure as possible, he wants to plan a route that passes through as many different treasure chambers as possible. Please tell Henry the maximum number of different treasure chambers such a route can visit.

Input Format

The first line contains three positive integers $N, R, C\ (1 \le N \le 10^5,\ 1 \le R, C \le 10^6)$.

The following $N$ lines each give the information of one teleportation gate, containing three positive integers $x_i, y_i, T_i$, meaning the gate is set in the treasure chamber at row $x_i$, column $y_i$, of type $T_i$. $T_i$ is an integer from $1$ to $3$: $1$ means a "Horizontal Gate" that can teleport to any column in row $x_i$; $2$ means a "Vertical Gate" that can teleport to any row in column $y_i$; $3$ means an "Any Gate" that can teleport to any of the 8 surrounding chambers.

It is guaranteed that $1 \le x_i \le R,\ 1 \le y_i \le C$, and all gate positions are distinct.

Output Format

One positive integer: the maximum number of different treasure chambers your route can pass through.

Sample Input

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1

Sample Output

9