지그재그

수열 $x(1), x(2), \ldots, x(k)$는 연속한 세 원소가 비증가 또는 비감소 순서를 이루지 않을 때 지그재그 수열이다. 더 정확히 말하면, 모든 $i = 1, 2, \ldots, k-2$에 대해 $x(i+1) < x(i)$이고 $x(i+1) < x(i+2)$이거나, $x(i+1) > x(i)$이고 $x(i+1) > x(i+2)$이어야 한다.

두 수열 $a(1), \ldots, a(n)$과 $b(1), \ldots, b(m)$이 주어진다. 두 수열에서 원소를 지워 서로 같게 만들고, 남은 수열이 지그재그 수열이 되도록 한다. 지워야 하는 원소 수의 최솟값이 $k$이면 답은 $m+n-k$이다. 가장 긴 공통 지그재그 부분수열의 길이를 구하라.

첫 줄에 $n$ ($1\leq n \leq 2000$)이 주어지고, 이어서 $n$개의 정수 $a(1), \ldots, a(n)$이 주어진다. 둘째 줄에는 $m$ ($1 \leq m \leq 2000$)이 주어지고, 이어서 $m$개의 정수 $b(1), \ldots, b(m)$이 주어진다. 모든 $a(i)$와 $b(i)$는 $[-10^9, 10^9]$ 범위에 있다.

$a$와 $b$의 가장 긴 공통 지그재그 부분수열의 길이를 한 줄에 출력한다.