Problem Description

Xiaoming found that there are many ways to split a very large positive integer into the sum of several positive integers. He chose two of these ways and listed them as two arrays $\{a_1, a_2, \cdots a_n\}$ and $\{b_1, b_2, \cdots b_m\}$. The sums of the two arrays are the same.

Define one merge operation as merging two adjacent numbers in an array into one new number, whose value is the sum of the original two numbers. Xiaoming wants to make the two arrays exactly the same after several merge operations, i.e., $n = m$ and for any index $i$, $a_i = b_i$. Please compute the minimum number of merge operations needed to achieve Xiaoming's goal.

Input Format

The input has $3$ lines.

The first line contains two positive integers $n, m$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ separated by spaces.

The third line contains $m$ integers $b_1, b_2, \cdots, b_m$ separated by spaces.

Output Format

Output $1$ line containing one integer.

4 3
1 2 3 4
1 5 4

1

Hint

Sample Explanation

You only need to merge $a_2$ and $a_3$. Array $a$ becomes $\{1,5,4\}$, which is the same as $b$.

Test Case Scale and Constraints

• For $20\%$ of the testdata, it is guaranteed that $n, m \le 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $n, m \le 10^5$, $0 < a_i, b_i \le 10^5$.

The 14th Lanqiao Cup Software Contest Final, C/C++ University Group B, Problem D.

Translated by ChatGPT 5