E. Бумага в клеточку
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечном клетчатом листе бумаги выбираются $$$n$$$ клеток и окрашиваются в три цвета, где $$$n$$$ кратно $$$3$$$. Оказывается, что есть ровно $$$\frac{n}{3}$$$ отмеченных клеток каждого из трех цветов!

Найдите наибольшее такое $$$k$$$, при котором можно выбрать $$$\frac{k}{3}$$$ клеток каждого цвета, удалить все остальные помеченные клетки, а затем выбрать три прямоугольника со сторонами, параллельными линиям сетки, так, чтобы выполнялись следующие условия:

  • Никакие два прямоугольника не могут пересекаться (но они могут иметь общую часть границы). Другими словами, площадь пересечения любых двух прямоугольников должна быть равна $$$0$$$.
  • $$$i$$$-й прямоугольник содержит все выбранные клетки $$$i$$$-го цвета и ни одной выбранной клетки другого цвета, для $$$i = 1, 2, 3$$$.
Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ — количество отмеченных клеток ($$$3 \leq n \le 10^5$$$, $$$n$$$ кратно 3).

В $$$i$$$-й из следующих $$$n$$$ строк содержится три целых числа $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$; $$$1 \leq c_i \leq 3$$$), где $$$(x_i, y_i)$$$ — координаты $$$i$$$-й отмеченной клетки, а $$$c_i$$$ — ее цвет.

Гарантируется, что все клетки $$$(x_i, y_i)$$$ попарно различны, и что существует ровно $$$\frac{n}{3}$$$ клеток каждого цвета.

Выходные данные

Выведите одно целое число $$$k$$$ — наибольшее количество клеток, которое можно оставить.

Примеры
Входные данные
9
2 3 1
4 1 2
2 1 3
3 4 1
5 3 2
4 4 3
2 4 1
5 2 2
3 5 3
Выходные данные
6
Входные данные
3
1 1 1
2 2 2
3 3 3
Выходные данные
3
Примечание

В первом примере можно оставить $$$6$$$ клеток с индексами $$$1, 5, 6, 7, 8, 9$$$.

Во втором примере можно оставить $$$3$$$ клетки с индексами $$$1, 2, 3$$$.