E. Мишка и таблица прямоугольников
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Лимака есть таблица из 2 строк и n столбцов. Ячейка j строки i содержит целое число ti, j, которое может быть положительным, отрицательным или нулем.

Непустой прямоугольник из ячеек назовем красивым, если и только если сумма чисел в его ячейках равна 0.

Лимак хочет выбрать несколько красивых прямоугольников и подарить их друзьям. Никакие два выбранных прямоугольника не могут иметь общих ячеек. Какое максимальное число красивых прямоугольников может выбрать Лимак?

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

В первой строке находится единственное целое число n (1 ≤ n ≤ 300 000) — количество столбцов в таблице.

Следующие две строки содержат числа, записанные в ячейках. i-я из этих строк содержит n целых чисел ti, 1, ti, 2, ..., ti, n ( - 109 ≤ ti, j ≤ 109).

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

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

Примеры
Входные данные
6
70 70 70 70 70 -15
90 -60 -30 30 -30 15
Выходные данные
3
Входные данные
4
0 -1 0 0
0 0 1 0
Выходные данные
6
Входные данные
3
1000000000 999999999 -1000000000
999999999 -1000000000 -999999998
Выходные данные
1
Примечание

В первом примере всего четыре красивых прямоугольника:

Лимак не может выбрать все их них, потому что они пересекаются. Он может выбрать максимум три прямоугольника: те, которые обведены синим на рисунке.

Во втором примере оптимально выбрать шесть красивых прямоугольников, каждый из них состоит из одной ячейки с числом 0.

В третьем примере единственный красивый прямоугольник — это вся таблица. Сумма всех чисел равна 0. Очевидно, Лимак может взять не больше одного красивого прямоугольника, поэтому ответ 1.