G. Звездная ночь в кемпинге
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У подножия горы Лиюшань будут установлены $$$n$$$ палаток, для тех, кто желает испытать радость от единения с природой, спокойствия ночи и яркого звездного неба.

Палатка номер $$$i$$$ будет расположена в точке $$$(x_i, y_i)$$$ и будет иметь вес $$$w_i$$$. Палатка считается важной, если оба $$$x_i$$$ и $$$y_i$$$ являются четными. Вам нужно убрать некоторые из палаток так, чтобы для каждой оставшейся важной палатки $$$(x, y)$$$ не существовало $$$3$$$ другие палатки $$$(x'_1, y'_1)$$$, $$$(x'_2, y'_2)$$$ и $$$(x'_3, y'_3)$$$, такие что оба условия выполнены:

  1. $$$|x'_j-x|, |y'_j - y|\leq 1$$$ для всех $$$j \in \{1, 2, 3\}$$$.
  2. Эти четыре палатки образуют параллелограмм (или прямоугольник), и одна из его сторон параллельна оси $$$x$$$.

Максимизируйте сумму весов оставшихся палаток.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1\leq n\leq 1\,000$$$), обозначающее количество палаток.

Каждая из следующих $$$n$$$ строк содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$-10^9\leq x_i,y_i \leq 10^9$$$, $$$1\leq w_i\leq 10^9$$$), обозначающие координаты $$$i$$$-й палатки и ее вес. Никакие две палатки не расположены в одной точке.

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

Выведите одно целое число — максимальную сумму весов оставшихся палаток.

Примеры
Входные данные
5
0 0 4
0 1 5
1 0 3
1 1 1
-1 1 2
Выходные данные
12
Входные данные
32
2 2 1
2 3 1
3 2 1
3 3 1
2 6 1
2 5 1
3 6 1
3 5 1
2 8 1
2 9 1
1 8 1
1 9 1
2 12 1
2 11 1
1 12 1
1 11 1
6 2 1
7 2 1
6 3 1
5 3 1
6 6 1
7 6 1
5 5 1
6 5 1
6 8 1
5 8 1
6 9 1
7 9 1
6 12 1
5 12 1
6 11 1
7 11 1
Выходные данные
24
Примечание

Иллюстрация для второго примера. Черные треугольники обозначают важные палатки. Этот пример также показывает все $$$8$$$ запрещенных паттернов.