Спадок Степана#12

Спадок Степана

1 second
256 megabytes
Medium

Степан отримав у спадок від дідуся стоянку з місць, пронумерованих від до . Стоянка розбита на дві частини. Перші місць знаходяться з лівого боку, а інші N - M місць з правого.

Кожного дня жителів цього району паркують свої автомобілі на стоянці Степана. Відомо, що перший житель приходить раніше усіх, потім другий, і так далі, тобто -й приходить -м. Також для кожного жителя відомо, скільки він буде платити, якщо його машину поставлять на -е місце.

Степан придбав розподільник місць, який кожному автомобілю, що приїздить вказує, на який бік паркуватись, після чого автомобіль паркується на мінімальне за номером вільне місце відповідного боку. При цьому Степан вирішив зекономити і не придбав програмне забезпечення для розподільника, тому він працює не оптимально.

Степан просить Вас написати програму для цього розподільника, яка максимізує доходи Степана.

Input

У першому рядку записані два цілих числа (2 \le N \le 1000) і (1 \le M < N) – загальна кількість місць на стоянці і кількість місць з лівого боку відповідно.

У кожному із наступних рядків записано по цілих додатних чисел. -е число -го рядка означає, скільки буде платити -ий житель за місце з номером на цій стоянці. Кожне з цих чисел не перевищує 10^6.

Output

Єдиний рядок має містити одне число – максимальний прибуток стоянки.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Не менш чим у 50% тестів N \le 30.