Ледяные дороги Номеля
Думаете, что ездить легко? Это не тот случай, когда дороги покрыты льдом.
В городе Номель расположено в точности n + 1 улица (дороги идут с запада на восток) и m + 1 авеню (дороги идут с севера на юг). Каждая улица пересекается с каждой авеню, таким образом каждая улица поделена на m кварталов, а каждая авеню поделена на n кварталов.
Сейчас зима, каждая дорога в городе покрыта толстым слоем льда. Поскольку ездить по льду достаточно сложно, на каждой дороге установлено собственное время проезда одного квартала. Это значение постоянно для всех кварталов одной дороги.
Естественно, Вы можете ездить только по дорогам. Ваша задача - найти путь с наименьшим временем, за которое можно добраться от северо-западного перекрестка города до юго-восточного. Этот путь также должен быть кратчайшим, то есть проходить в точности по n + m кварталам.
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 500 000). Во второй строке находятся n + 1 натуральное число, задающих время передвижения по улицам Номеля в порядке с севера на юг. Третья строка содержит m + 1 натуральное число, задающих время передвижения по авеню Номеля в порядке с запада на восток. Гарантируется, что ни одно из этих чисел не превосходит 10^9.
Выходные данные
Вывести одно число - наименьшее требуемое время проезда.