У Лимака есть таблица из 2 строк и n столбцов. Ячейка j строки i содержит целое число ti, j, которое может быть положительным, отрицательным или нулем.
Непустой прямоугольник из ячеек назовем красивым, если и только если сумма чисел в его ячейках равна 0.
Лимак хочет выбрать несколько красивых прямоугольников и подарить их друзьям. Никакие два выбранных прямоугольника не могут иметь общих ячеек. Какое максимальное число красивых прямоугольников может выбрать Лимак?
Выходные данные
Выведите одно целое число — максимальное число непересекающихся по ячейкам красивых прямоугольников.
Примечание
В первом примере всего четыре красивых прямоугольника:
Лимак не может выбрать все их них, потому что они пересекаются. Он может выбрать максимум три прямоугольника: те, которые обведены синим на рисунке.
Во втором примере оптимально выбрать шесть красивых прямоугольников, каждый из них состоит из одной ячейки с числом 0.
В третьем примере единственный красивый прямоугольник — это вся таблица. Сумма всех чисел равна 0. Очевидно, Лимак может взять не больше одного красивого прямоугольника, поэтому ответ 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
70 70 70 70 70 -15
90 -60 -30 30 -30 15
|
3
|
|
2
|
4
0 -1 0 0
0 0 1 0
|
6
|
|
3
|
3
1000000000 999999999 -1000000000
999999999 -1000000000 -999999998
|
1
|