Limak 有一个由 2 行 n 列组成的网格。第 i 行中的第 j 个单元格包含一个整数 ti, j,可以是正数、负数或零。
当且仅当单元格中的数字总和等于 0 时,非空单元格矩形才被称为良好。
Limak 想选择一些漂亮的矩形并将它们作为礼物送给他的朋友。任何两个选定的矩形不应共享一个单元格。 Limak 最多可以选择多少个漂亮的矩形?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 300 000) — 网格中的列数。
接下来的两行包含网格中的数字。这两行中的第 i 行包含 n 个整数 ti, 1, ti, 2, ..., ti, n (- 109 ≤ ti, j ≤ 109)。
输出
打印一个整数,表示单元不相交的漂亮矩形的最大可能数量。
示例
输入 #1
6 70 70 70 70 70 -15 90 -60 -30 30 -30 15
输出 #1
3
输入 #2
4 0 -1 0 0 0 0 1 0
输出 #2
6
输入 #3
3 1000000000 999999999 -1000000000 999999999 -1000000000 -999999998
输出 #3
1
注意
在第一个示例中,有四个漂亮的矩形:
Limak 无法选择所有这些,因为它们不是不相交的。他应该选取三个漂亮的矩形:那些在图纸上标记为蓝色框的矩形。
在第二个示例中,最好选择六个漂亮的矩形,每个矩形由一个数字为 0 的单元格组成。
在第三个示例中,唯一的好矩形是整个网格 - 所有数字的总和为 0。显然,Limak 最多可以选择一个好矩形,因此答案为 1。