Белые медведи Меньшиков и Услада из Санкт-Петербургского зоопарка и слоник Хорас из Киевского зоопарка решили заняться живописью. В рамках создания своего первого шедевра они уже нарисовали на бумаге эскиз, который состоит из n отрезков. Каждый отрезок был либо горизонтальный, либо вертикальный. Теперь друзья хотят упростить этот эскиз, стерев некоторые отрезки или части отрезков, так чтобы окончательное творение удовлетворяло трем условиям:
- Хорас хочет иметь возможность нарисовать всю картину, поставив кисть на холст только один раз и не отрывая ее, пока картина не будет закончена (нет ничего плохого в том, чтобы при этом провести кистью несколько раз по одному месту). Поэтому все оставшиеся отрезки должны образовывать единую связную фигуру.
- Меньшиков хочет, чтобы получившаяся фигура была простой. Простой фигурой он называет фигуру, которая не содержит ни одного цикла.
- Изначально все отрезки на эскизе имеют целочисленные координаты точек начала и конца. Услада не любит вещественные координаты и хочет, чтобы это условие выполнялось и после стирания.
Так как в остальном их эскиз уже прекрасен, то друзья решили стереть такие части эскиза, чтобы максимизировать сумму длин оставшихся отрезков. От вас требуется посчитать эту максимальную сумму длин оставшихся после стирания отрезков.
Выходные данные
Выведите единственное целое число — максимальную сумму длин оставшихся отрезков.
Примечание
Фигуры, которые можно получить в двух данных примерах:
В первом примере необходимо стереть любой из отрезков, так как два отрезка вместе не образуют единую связную фигуру.
Во втором примере изначальные отрезки образуют цикл, есть четыре способа разорвать этот цикл — стереть первый, второй или четвертый отрезок полностью или стереть середину третьего отрезка. Последний вариант изображен на рисунке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
0 0 0 1
1 0 1 1
|
1
|
|
2
|
4
0 0 1 0
0 0 0 1
1 -1 1 2
0 1 1 1
|
5
|