Two Towers

Interview

Time limit1sMemory limit128 MB

Summary

Remove the fewest blocks from the tops of two towers so the remaining towers have equal height.

Level: Easy3 of 10
Topics: Greedy, Two pointers, Prefix sum
Solved: No attempts yet

Problem

Little Bajtek received a set of blocks from his grandfather. Each block has a certain height. Bajtek stacks the blocks one on top of another to form a tower. Using all of his blocks, he built two towers.

Now he wonders what is the minimum number of blocks he has to remove so that both towers have the same height. Blocks may be removed only from the top of each tower, and no new blocks may be added. In particular, it is allowed to remove all of the blocks from a tower. If every block is removed from both towers, both heights become 0 and are therefore equal.

Input

The first line contains two integers $n$ , $m$ ( $1 \le n, m \le 10^6$ ), the number of blocks in the first and the second tower respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ), where $a_i$ is the height of the $i$ -th block of the first tower counting from the bottom; $a_1$ is the bottom block and $a_n$ is the top block.

The third line contains $m$ integers $b_1, b_2, \dots, b_m$ ( $1 \le b_i \le 10^9$ ), where $b_i$ is the height of the $i$ -th block of the second tower counting from the bottom; $b_1$ is the bottom block and $b_m$ is the top block.

Output

Print a single integer: the minimum number of blocks that must be removed so that both towers have the same height.

Hint

Examples3

Example 1
Input
```
4 3
2 2 1 2
1 3 2
```
Expected output
```
3
```
Example 2
Input
```
2 1
1 2
3
```
Expected output
```
0
```
Example 3
Input
```
1 1
5
3
```
Expected output
```
2
```