Задан массив из $n$ элементов и число $k$. Разбейте заданный массив на $k$ подмассивов (которые содержат в себе все элементы). Вычислим максимум среди сумм элементов всех $k$ подмассивов. Разбиение следует провести так, чтобы это значение было как можно меньшим. Найдите этот максимум. \InputFile Первая строка содержит два числа $n$ и $k~(n \le 10^6, 1 \le k \le n)$. Вторая строка содержит $n$ натуральных чисел, каждое из которых не более $10^9$. \OutputFile Выведите наименьшее возможное значение среди максимумов сумм элементов всех $k$ подмассивов. \includegraphics{https://static.e-olymp.com/content/fa/fa4249eaba38a60e358e745a9a784883ce10a68c.gif} \Example Для первого примера оптимальным разбиением будет $\{1, 2\}, \{3\}, \{4\}$. Максимум сумм элементов среди всех подмассивов равен $4$, который является наименьшим возможным для $3$ подмассивов. Для второго примера оптимальным разбиением будет $\{1, 2, 3, 4\}, \{2, 3, 4\}, \{2, 3, 1\}$. Максимум сумм элементов среди всех подмассивов равен $10$, который является наименьшим возможным для $3$ подмассивов.