ЗАДАЧА 2.2. ИГРА

Малкият Иванчо обича да играе през свободното си време. За съжаление, не винаги може да се наслаждава на компанията на приятелите си и понякога се отегчава, когато е сам. Затова измисля игри, в които е единственият играч. Особено е горд с последната си игра и иска да ви разкаже за нея.

Дадени са две крайни редици от положителни цели числа. Играта се състои в последователни ходове. Позволено ви е да правите следния ход. Премахвате последните  K1 числа (K1≥1) от първата редица (възможно е това да бъде дори цялата редица) и намирате сумата им S1; след това премахвате последните K2 числа (K2≥1) от втората редица (отново може да премахнете цялата редица) и намирате сумата им S2. След това изчислявате цената на хода като (S1‑K1)*(S2-K2). Продължавате да правите ходове, докато премахнете всички числа от двете редици. Общата цена на играта е сумата от цените на нейните ходове. Целта ви е да минимизирате общата цена. Не е позволено да оставите една от редиците празна, ако другата не е.

След като научавате правилата от Иван, вие решавате, че е необходима помощта на компютър, така че написвате програма GAME, която изчислява минималната цена на играта.

Входните данни се четат от стандартния вход и се състоят от три реда. Първият ред съдържа две цели числа L1 и L2 (1 ≤ L1, L2 ≤ 2000), отделени с интервал, които представляват дължините на двете редици. Вторият ред съдържа L1 цели числа, отделени с интервал, които са елементите на първата редица. Третият ред съдържа L2 цели числа, отделени с интервал, които са елементите на втората редица. Елементите на редиците не надвишават 1000.

Програмата ви трябва да изведе на стандартния изход един ред, който съдържа едно число – минималната цена на играта, описана по-горе.

ПРИМЕР

Вход 3 2 1 2 3 1 2

Изход 2