Степан показує речення з \(N\) слів у вікні. Усі слова мають однакову висоту, а ширина \(i\)-го слова \((1≤i≤N)\) дорівнює \(L_i ​\).

Слова відображаються у вікні, розділеному пробілом шириною 1. Точніше, коли речення відображається у вікні шириною \(W\), наступні умови задовольняються.

• Речення поділено на кілька рядків.
• Перше слово відображається на початку верхнього рядка.
• \(i\)-те слово \((2≤i≤N)\) відображається або з проміжком 1 після \((i−1)\)-го слова, або на початку рядка під рядком, що містить \((i−1)\)-е слово. Воно більше ніде не відображатиметься.
• Ширина кожного рядка не перевищує \(W\). Тут ширина рядка відноситься до відстані від лівого кінця крайнього лівого слова до правого кінця крайнього правого слова.

Коли Степан показував речення у вікні, речення містилося в \(M\) або менше рядків. Знайдіть мінімально можливу ширину вікна.

Обмеження

• \(1≤M≤N≤2×10^5\)
• \(1≤L_i ​ ≤10^9\)  \((1≤i≤N)\)
• Усі вхідні значення є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\).

Наступний   рядок містить цілі числа \(L_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Приклад вихідних даних

26

Коли ширина вікна становить 26 подане речення можна розмістити в трьох рядках

Приклад вхідних даних

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Приклад вихідних даних

10000000009

Приклад вхідних даних

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Приклад вихідних даних

189