칠판

면접 대비

시간 제한1초메모리 제한128 MB

요약

두 이진 수열에서 모두 부분 수열이 되는 0 뒤에 1이 이어지는 가장 긴 수열의 길이를 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

Kacper와 Adi는 이진법을 무척 좋아하게 되었습니다. 두 사람은 각자 칠판에 0과 1로 이루어진 수열을 하나씩 적었습니다. 이제 Kacper는 두 수열에서 각각 일부 숫자를 지워서, 남은 두 수열이 서로 완전히 같으면서 동시에 '정렬된' 상태가 되게 만들고 싶습니다. 여기서 정렬되었다는 것은, 처음으로 1이 등장한 뒤에는 더 이상 0이 나오지 않는다는 뜻입니다. 칠판에 남길 수 있는 가장 긴 수열의 길이는 얼마일까요?

입력

첫째 줄에 두 정수 $n$ , $m$ ( $1 \le n, m \le 10^6$ )이 주어집니다. 각각 Kacper와 Adi가 적은 수열의 길이입니다.

둘째 줄에는 Kacper가 적은 수열이 공백으로 구분된 $n$ 개의 숫자(각 숫자는 0 또는 1)로 주어집니다.

셋째 줄에는 Adi가 적은 수열이 공백으로 구분된 $m$ 개의 숫자(각 숫자는 0 또는 1)로 주어집니다.

출력

칠판에 남길 수 있는 가장 긴 수열의 길이를 한 줄에 하나의 정수로 출력합니다. 아무것도 남길 수 없다면 $0$ 을 출력합니다.

예제3

예제 1
입력
```
6 6
0 0 1 1 0 1
0 1 0 0 1 1
```
예상 출력
```
4
```
예제 2
입력
```
2 2
0 0
1 1
```
예상 출력
```
0
```
예제 3
입력
```
1 1
0
0
```
예상 출력
```
1
```