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