Занулення

Limits: 2 sec., 512 MiB

У Зеника є два масиви — \(a\) та \(b\), кожен довжиною \(n\). Йому потрібно занулити всі елементи масиву \(a\).

За одну операцію, Зеник може зменшити будь-яке значення \(a_i\) на 1. Така операція буде йому коштувати \(b_i\) гривень.

На щастя, йому погодилася допомогти Марічка. Вона вміє у будь-який момент зробити циклічний зсув масиву \(a\) вправо. Але Марічка дуже зайнята, тому вона може зробити це не більше ніж \(k\) разів.

План наступний: спершу Зеник зробить якісь віднімання. Тоді прийде Марічка і зробить циклічний зсув масиву \(a\): перший елемент масиву a стане рівним останньому елементу, другий елемент стане рівним першому, третій — другому, і т.д. Зверніть увагу, що Марічка зсовує лиш масив \(a\), лишаючи масив \(b\) незмінним. Після цього Зеник знову зробить якісь віднімання. Далі знову прийде Марічка і зробить ще один циклічний зсув, після чого Зеник продовжить віднімати. І т.д. Загалом Марічка може зробити не більше ніж \(k\) циклічних зсувів.

Потрібно визначити, яку мінімальну суму Зеник заплатить, щоб після всіх можливих зсувів і віднімань усі елементи масиву \(a\) стали рівні нулю.

Input

У першому рядку задано 2 цілі числа \(n\) та \(k\) — розмів масиву та кількість операцій, які може зробити Марічка.

У наступному рядку задано \(n\) цілих чисел — масив \(a\).

У наступному рядку задано \(n\) цілих чисел — масив \(b\).

Output

Виведіть одне ціле число — мінімальну ціну занулення масиву \(a\).

Constraints

\(1 \leq n \leq 5 \cdot 10^5\),

\(0 \leq k \leq 10^9\),

\(0 \leq a_i, b_i \leq 10^6\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 8 балів: \(k = 0\),

• 11 балів: \(k \geq n\),

• 20 балів: \(n, k \leq 10^3\),

• 24 балів: \(b_i \leq b_{i+1}\),

• 36 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 2 4 7 4 7 1 2 2 1	22

Notes

У даному прикладі мінімальної ціни можна досягнути наступним чином:

1. Відняти 4 від першого елемента та 7 від останнього, заплативши \(4 \cdot 1 + 7 \cdot 1 = 11\). Після цього масив стане \((0, 7, 4, 0)\).

2. Виконати циклічний зсув вправо — \((0, 0, 7, 4)\).

3. Відняти 4 від останнього елемента, заплативши \(4 \cdot 1 = 4\), масив стане \((0, 0, 7, 0)\).

4. Виконати циклічний зсув вправо — \((0, 0, 0, 7)\).

5. Відняти 7 від останнього елемента, заплативши \(7 \cdot 1 = 7\), масив стане \((0, 0, 0, 0)\).

Ціна, що була заплачена, дорівнює \(11 + 4 + 7 = 22\).