← 返回题目列表

Codeforces · 950/B

B. 截获的消息

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

黑客 Zhorik 想要破译他昨天截获的两条秘密消息。是的,消息是一系列加密块,每个块由几个字节的信息组成。

Zhorik 知道每条消息都是包含一个或多个文件的存档。 Zhorik 知道这些档案中的每一个是如何通过网络传输的:如果一个档案由 k 个大小为 l1, l2, ..., lk 字节的文件组成,则第 i 个文件被分割为一个或多个块 bi, 1, bi, 2, ..., bi, mi (这里块的总长度 bi, 1 + bi, 2 + ... + bi, mi 等于文件 li 的长度),之后所有块都通过网络传输,保持文件的顺序档案。

Zhorik 认为这两条消息包含相同的存档,因为它们的总长度相等。然而,每个文件可以在两条消息中以不同的方式分割成块。

您将获得两条消息中每条消息中块的长度。如果 Zhorik 的假设正确,请帮助 Zhorik 确定存档中可以包含的最大文件数。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 105) — 第一个和第二个消息中的块数。

第二行包含 n 个整数 x1, x2, ..., xn (1 ≤ xi ≤ 106) — 构成第一条消息的块的长度。

第三行包含 m 个整数 y1, y2, ..., ym (1 ≤ yi ≤ 106) — 构成第二条消息的块的长度。

保证 x1 + ... + xn = y1 + ... + ym。此外,还保证 x1 + ... + xn ≤ 106。

输出

打印截获数组可以包含的最大文件数。

示例

输入 #1

7 6
2 5 3 1 11 4 4
7 8 2 4 1 8

输出 #1

3

输入 #2

3 3
1 10 100
1 100 10

输出 #2

2

输入 #3

1 4
4
1 1 1 1

输出 #3

1

注意

在第一个示例中,存档中的最大文件数为 3。例如,存档中可能存在大小为 2 + 5 = 7、15 = 3 + 1 + 11 = 8 + 2 + 4 + 1 和 4 + 4 = 8 的三个文件。

在第二个示例中,存档可能包含两个大小为 1 和 110 = 10 + 100 = 100 + 10 的文件。请注意,通过网络传输存档时会保持文件的顺序,因此我们不能说存在大小为 1、10 和 100 的三个文件。

在第三个示例中,唯一的可能性是存档包含大小为 4 的单个文件。