Naleśniki

Limit pamięci: 32MB

Bajtek i Bitek, bracia bliźniacy, często rywalizują ze sobą o różne rzeczy. Dzisiaj mama usmażyła im naleśniki i położyła je na dwóch talerzach. Na obu talerzach naleśniki są ułożone w stos, czyli zdejmować je można wyłącznie po jednym od góry. Bracia znają smakowitość każdego z naleśników na obu talerzach. Bajtek chce się dowiedzieć ile wynosi maksymalna suma smakowitości naleśników, które może wybrać, jeśli on (Bajtek) zaczyna i jego brat (Bitek) będzie wybierać swoje naleśniki możliwie optymalnie. Ustalił z bratem, że naleśniki zdejmują na zmianę po jednym z góry dowolnego z talerzy.

Zadanie:

Wejście:

W pierwszej linii znajdują się dwie liczby całkowite: n i m (1 <= n, m <= 2000). W następnych dwóch liniach znajdują się opisy dwóch talerzy naleśników. Pierwszy składa się z n liczb całkowitych, a drugi z m. Są to smakowitości poszczególnych naleśników. Smakowitości będa należeć do przedziału <-1000; 1000>. Opisy zaczynają się od spodu talerza.

Wyjście:

Jedna liczba, będąca maksymalną sumą smakowitości naleśników, jakie Bajtek może wybrać.

Przykład:

wejście:
3 3
2 7 -5
10 -2 -3

wyjście:
2

Wyjaśnienie przykładu:

-5
7
2		-3
-2
10
Talerz 1 (n)Talerz 2 (m)

Czynności:
Bajtek zdejmuje naleśnik ze smakowitością -3
Bitek -5
Bajtek 7
Bitek 2
Bajtek -2
Bitek 10

Bajtek uzbierał naleśniki: -3 + 7 + -2 = 2
Bitek uzbierał naleśniki: -5 + 2 + 10 = 7