The Board

Interview

Time limit1sMemory limit128 MB

Summary

Find the longest string of zeros followed by ones that appears as a subsequence of both given binary sequences.

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

Problem

Kacper and Adi have grown very fond of the binary system. Each of them wrote a sequence of zeros and ones on the board. Kacper now wants to cross out some digits in each sequence so that the two remaining sequences are identical and, at the same time, sorted. Sorted means that after the first occurrence of a one, no zero may appear. What is the length of the longest sequence that can remain on the board?

Input

The first line contains two integers $n$ , $m$ ( $1 \le n, m \le 10^6$ ), the lengths of the sequences written by Kacper and Adi, respectively.

The second line contains Kacper's sequence as $n$ digits (each 0 or 1) separated by spaces.

The third line contains Adi's sequence as $m$ digits (each 0 or 1) separated by spaces.

Output

Print a single integer: the length of the longest sequence that can remain on the board. Print $0$ if nothing can remain.

Examples3

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