Zrinka

Time limit1sMemory limit1024 MB

Summary

Assign distinct positive integers, even for each 0 and odd for each 1, so both arrays increase, and minimize the largest value used.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

You are given two arrays of length $n$ and $m$ , each containing only $0$ and $1$ .

Replace every $0$ with a positive even integer and every $1$ with a positive odd integer. After the replacement, both arrays must be increasing, and each positive integer may be used at most once.

Since this would be too easy, the largest number you use must be as small as possible. Given the two arrays, output the minimum possible largest number.

Input

The first array has length $n$ ( $0 \le n \le 5\,000$ ), and the second has length $m$ ( $1 \le m \le 5\,000$ ).

The first line contains $n + 1$ integers. The first integer is $n$ , and the rest are the elements of the first array.

The second line contains $m + 1$ integers. The first integer is $m$ , and the rest are the elements of the second array.

Output

Print one positive integer on the first and only line: the answer to the question above.

Hint

Clarification of the second example: One of the possible solutions is $(2, 3, 4, 5)$ and $(1, 6, 8, 9)$ .

Clarification of the third example: One of the possible solutions is $(2, 3, 6, 8, 9)$ and $(4, 10, 12, 13)$ .

Examples3

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