Поликарп тренирует свое умение решать задачи. У него есть список из $$$n$$$ задач со сложностями $$$a_1, a_2, \dots, a_n$$$ соответственно. Его план состоит в том, чтобы тренироваться ровно $$$k$$$ дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно $$$n$$$ задач ровно за $$$k$$$ дней.

Таким образом, каждый день Поликарп решает последовательность подряд идущих (последовательных) задач с самого начала списка. Он не может пропускать задачи или решать их несколько раз. В итоге за $$$k$$$ дней он решит $$$n$$$ задач.

Полезность $$$j$$$-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение $$$j$$$-го дня (то есть если он решит задачи с номерами от $$$l$$$ до $$$r$$$ в течение какого-то дня, тогда полезность этого дня равна $$$\max\limits_{l \le i \le r}a_i$$$). Общая полезность его тренировки — это сумма полезностей по всем $$$k$$$ дням его тренировки.

Вы хотите помочь Поликарпу получить максимально возможную общую полезность среди всех доступных способов решить задачи. Ваша задача — распределить $$$n$$$ задач по $$$k$$$ дням таким образом, что это распределение удовлетворяет ограничениям, описанным выше, и общая полезность является максимально возможной.

Например, если $$$n = 8, k = 3$$$ и $$$a = [5, 4, 2, 6, 5, 1, 9, 2]$$$, одним из возможных способов с максимальной общей полезностью является следующий: $$$[5, 4, 2], [6, 5], [1, 9, 2]$$$. Здесь общая полезность равна $$$5 + 6 + 9 = 20$$$.