카드게임

지훈이는 혼자 하는 카드게임을 즐긴다. 카드 한 장에는 양의 정수가 하나 적혀 있고, 같은 수가 적힌 카드가 여러 장 있을 수도 있다. 게임은 짝수 장의 카드를 무작위로 섞은 뒤 같은 장수의 두 더미로 나누어 하나는 왼쪽에, 다른 하나는 오른쪽에 놓고 시작한다. 옆에는 버린 카드를 담을 빈 통을 하나 둔다.

두 더미의 맨 위 카드를 서로 비교하며 게임을 진행한다. 왼쪽 더미의 맨 위 카드를 왼쪽 카드, 오른쪽 더미의 맨 위 카드를 오른쪽 카드라고 하자. 규칙은 다음과 같다.

1. 언제든지 왼쪽 카드만 통에 버릴 수 있고, 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작으면 오른쪽 카드만 통에 버릴 수도 있다. 이때는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. 규칙 1과 규칙 2에 따라 진행하다가 어느 한 더미라도 카드가 남지 않으면 게임이 끝나고, 그때까지 얻은 점수의 합이 최종 점수가 된다.

다음은 세 장씩 두 더미로 게임을 시작하는 경우다.

처음에는 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 1에 따라 왼쪽 카드만 버리거나 두 장을 모두 버릴 수 있고, 규칙 2에 따라 오른쪽 카드만 버릴 수도 있다. 오른쪽 카드만 버리면 2점을 얻는다. 이제 오른쪽 카드는 4이고 왼쪽 카드 3보다 크므로 규칙 1의 두 가지만 남는다. 두 장을 모두 버리면 왼쪽 카드는 2, 오른쪽 카드는 1이 된다. 여기서 왼쪽 카드만 버리면 왼쪽 카드는 5, 오른쪽 카드는 1이 된다. 다시 오른쪽 카드만 버리면 1점을 얻고, 오른쪽 더미가 비었으므로 규칙 3에 따라 게임이 끝난다. 이렇게 고르면 최종 점수는 $2 + 1 = 3$이다. 같은 배치에서 가장 잘 고르면 최종 점수는 7이 된다.

두 더미의 카드가 주어질 때 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오.

첫 줄에 한 더미의 카드 개수 $N$ ($1 \le N \le 2000$)이 주어진다. 둘째 줄에 왼쪽 더미의 카드에 적힌 정수 $A$ ($1 \le A \le 2000$)가 맨 위 카드부터 차례대로 $N$개 주어진다. 셋째 줄에 오른쪽 더미의 카드에 적힌 정수 $B$ ($1 \le B \le 2000$)가 맨 위 카드부터 차례대로 $N$개 주어진다. 한 더미에 같은 수가 적힌 카드가 두 장 이상 있을 수 있다.

얻을 수 있는 최종 점수의 최댓값을 한 줄에 출력한다.