Ледяные дороги Номеля#6445

Ледяные дороги Номеля

1 секунда
256 мегабайт
Easy

Думаете, водить машину легко? Только не тогда, когда улицы покрыты льдом.

В городе Номел есть ровно N+1 улиц, идущих с запада на восток, и M+1 проспектов, идущих с севера на юг. Каждая улица пересекается с каждым проспектом, разделяя каждую улицу на кварталов, а каждый проспект — на кварталов.

Наступила зима, и все дороги покрыты толстым слоем льда. Поскольку ездить по льду трудно, для каждой улицы и каждого проспекта задано фиксированное время проезда одного квартала. Это время одинаково для всех кварталов на одной улице или на одном проспекте.

Передвигаться можно только по улицам и проспектам. Ваша задача — определить минимальное общее время, необходимое для того, чтобы проехать от северо-западного пересечения города до юго-восточного, двигаясь по кратчайшему маршруту, проходящему ровно через N+M кварталов.

Input

Первая строка содержит два целых числа и (1 \le N, M \le 500\ 000). Вторая строка содержит N+1 положительных целых чисел — время проезда по каждой улице (перечислены с севера на юг). Третья строка содержит M+1 положительных целых чисел — время проезда по каждому проспекту (перечислены с запада на восток). Ни одно значение не превышает 10^9.

Output

Выведите одно число — минимально возможное общее время проезда.

Examples

Example 1

Loading
Loading