인비저블

친구와 "인비저블"이라는 카드 게임을 하려고 한다. 이 게임에는 "득점 카드"와 "방해 카드" 두 종류의 카드가 있다. 각 득점 카드에는 양의 값이 적혀 있다. 게임 규칙은 다음과 같다.

• 게임은 플레이어 1과 플레이어 2, 두 명이 진행한다. 게임은 플레이어 1의 턴부터 시작한다.
• 장에는 스택 하나와 덱 두 개가 있다. 스택은 두 플레이어가 놓은 카드로 이루어진다. 각 플레이어의 덱은 그 플레이어가 가진 득점 카드와 방해 카드로 이루어진다. 플레이어는 자신의 덱이나 상대 덱의 카드 순서를 언제든지 확인할 수 있다. 게임 시작 시점에 스택에는 카드가 한 장도 없다.
• 두 플레이어는 번갈아 가며 다음 두 행동 중 하나를 정확히 한 번 한다.
  • 자신의 덱 맨 위 카드를 스택 맨 위에 놓는다. 자신의 덱에 카드가 한 장도 없으면 이 행동은 할 수 없다.
  • 자신의 턴을 패스한다.
• 플레이어가 턴을 패스하면 다음 처리를 한다.
  • 각 플레이어는 스택에 있는 득점 카드 중 다음 두 조건을 모두 만족하는 카드를 전부 얻는다. 얻은 득점 카드는 장에서 제거된다.
    1. 자신이 스택에 놓은 득점 카드이다.
    2. 상대가 놓은 어떤 방해 카드보다 위에 있다. (스택에 상대의 방해 카드가 없으면 자신이 스택에 놓은 카드를 전부 얻는다.)
  • 스택의 카드를 모두 제거한다.

스택에 카드가 없는 상태에서 두 플레이어가 연속으로 패스하면 게임이 끝난다. 각 플레이어의 최종 점수는 자신이 얻은 득점 카드에 적힌 수의 합이다.

각 플레이어는 자신의 점수에서 상대 점수를 뺀 값을 최대화하도록 최적으로 행동한다. 주어진 두 덱에 대해, 두 플레이어가 최적으로 행동했을 때 플레이어 1의 점수에서 플레이어 2의 점수를 뺀 값을 구하라.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

n m
a_1 a_2 ... a_n
b_1 b_2 ... b_m

첫째 줄에는 덱의 장 수를 나타내는 양의 정수 $n$, $m$ ($1 \le n, m \le 50$)이 주어진다. 둘째 줄에는 플레이어 1의 덱을 위에서부터 차례대로 나타낸 $a_1, a_2, \dots, a_n$이 주어진다. 셋째 줄에는 플레이어 2의 덱을 위에서부터 차례대로 나타낸 $b_1, b_2, \dots, b_m$이 주어진다. 각 값은 1 이상 1,000,000 이하의 정수이거나 -1이다. 양수는 득점 카드를, -1은 방해 카드를 나타낸다.

두 플레이어가 최적으로 행동했을 때 (플레이어 1의 점수) - (플레이어 2의 점수) 값을 출력한다.