熊与矩形条带

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Limak 有一个由 $2$ 行 $n$ 列组成的网格。第 $i$ 行第 $j$ 列的单元格中写有整数 $t_{i,j}$，它可以是正数、负数或零。

一个非空矩形称为好矩形，当且仅当其中所有单元格的数字之和为 $0$。矩形的边必须与网格线重合，因此它只能占据第一行的一段、第二行的一段，或两行中列区间相同的一段。

Limak 想选择若干个好矩形，并要求任意两个被选择的矩形没有公共单元格。请计算最多能选择多少个好矩形。

输入格式

第一行一个整数 $n$，表示网格的列数。

接下来两行描述网格。第 $i$ 行包含 $n$ 个整数 $t_{i,1},t_{i,2},\ldots,t_{i,n}$。

输出格式

输出一个整数，表示两两不相交的好矩形的最大数量。

样例输入 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

数据范围

$1\le n\le300000$，$-10^9\le t_{i,j}\le10^9$。

每个测试点独立计分。