O. Первоапрельская задача (сложная)
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Планы для HC2 довольно надуманны: остаётся чуть более чем 500 000 дней до HC2 3387, например, и, соответственно, мы планируем сделать несколько сотен тысяч задач в соответствующем году (мы надеемся, что соревнования по программированию станут более популярными). Суркам нужно приступать к работе, и они могли бы использовать хороший план ...

Входные данные

Входные данные те же, что и в средней версии этой задачи, но изменены ограничения: 1 ≤ k ≤ n ≤ 500 000.

Выходные данные

Выходные данные те же, что и в средней версии этой задачи.

Пример
Входные данные
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
Выходные данные
32