← 返回题目列表

Codeforces · 1036/D

D. Vasya 和数组

中文机器翻译题面 查看原题

Vasya 有两个数组 $$$A$$$ 和 $$$B$$$,长度分别为 $$$n$$$ 和 $$$m$$$。

他可以任意次数(可能为零)执行以下操作:他获取数组的某个连续子段并将其替换为单个元素,该元素等于该子段上所有元素的总和。例如,从数组 $$$[1, 10, 100, 1000, 10000]$$$ Vasya 可以获取数组 $$$[1, 1110, 10000]$$$,从数组 $$$[1, 2, 3]$$$ Vasya 可以获取数组 $$$[6]$$$。

两个数组 $$$A$$$ 和 $$$B$$$ 被视为相等当且仅当它们具有相同的长度并且对于每个有效的 $$$i$$$ $$$A_i = B_i$$$。

Vasya 想要对数组 $$$A$$$ 执行一些操作,对数组 $$$B$$$ 执行一些操作,以使数组 $$$A$$$ 和 $$$B$$$ 变得相等。此外,结果数组的长度应该尽可能大。

帮助 Vasya 确定他可以达到的数组的最大长度或输出不可能使数组 $$$A$$$ 和 $$$B$$$ 相等。

输入

第一行包含一个整数 $$$n~(1 \le n \le 3 \cdot 10^5)$$$ — 第一个数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \cdots, a_n~(1 \le a_i \le 10^9)$$$ — 数组 $$$A$$$ 的元素。

第三行包含一个整数 $$$m~(1 \le m \le 3 \cdot 10^5)$$$ — 第二个数组的长度。

第四行包含 $$$m$$$ 整数 $$$b_1, b_2, \cdots, b_m~(1 \le b_i \le 10^9)$$$ - 数组 $$$B$$$ 的元素。

输出

打印单个整数 - 对数组 $$$A$$$ 和 $$$B$$$ 执行某些操作以使它们变得相等后所得数组的最大长度。

如果无法使数组相等,则打印“-1”。

示例

输入 #1

5
11 2 3 5 7
4
11 7 3 7

输出 #1

3

输入 #2

2
1 2
1
100

输出 #2

-1

输入 #3

3
1 2 3
3
1 2 3

输出 #3

3