Чаробњак Миливоје поседује \(N\) магичних напитака поређаних у низ. За сваки од тих \(N\) напитака дата је његова моћ \(a_i\). Миливоје жели да искомбинује ове напитке у један и тако призове моћну чин. Он зна да му је за то потребно да прво одабере тачно \(K\) од постојећих \(N\) напитака и остале остави по страни. Дакле, Миливоје изабере \(K\) напитака, остале одбаци, а изабраним напицима не мења редослед. Потом Миливоје комбинује тих \(K\) напитака све док му не остане само један.

Да би се спречило што више несрећа на послу, чаробњаци су на међународном конгресу усвојили веома строга правила о томе како се напици смеју мешати. Та правила су следећа:

• Могуће је узети последњи напитак из низа и насути цео напитак у бочицу која садржи први напитак. У том случају моћ првог напитка постаје разлика моћи првог и последњег напитка. Дакле, уколико је први напитак имао моћ \(x\), а последњи моћ \(y\), при овој операцији последњи напитак се уклања из низа, а моћ првог напитка постаје \(x-y\).
• Могуће је узети први напитак из низа и насути цео напитак у бочицу која садржи последњи напитак. У том случају моћ последњег напитка постаје разлика моћи последњег и првог напитка. Дакле, уколико је први напитак имао моћ \(x\), а последњи моћ \(y\), при овој операцији први напитак се уклања из низа, а моћ последњег напитка постаје \(y-x\).

Приметити да применом ових операција моћ неког напитка може постати и негативна. У оба случаја један напитак се потроши, тј. број напитака у низу се смањи за један. У сваком тренутку Миливоје може да бира које ће од правила користити. Он ће овај процес поновити \(K-1\) пута, тј. све док у низу не остане само један напитак. Како Миливоје жели да призове што моћнију чин, њега интересује која је највећа могућа моћ напитка који може остати након примене свих операција. Миливоје је један од најбољих чаробњака на свету и уколико му помогнете, он ће бацити чин која ће Вам донети \(100\) поена на овом задатку.

Опис улаза

У првом реду стандардног улаза налазе се два позитивна цела броја \(N\) и \(K\) - број напитака на почетку и број напитака које Миливоје треба да изабере.

У другом реду стандардног улаза, налази се \(N\) целих бројева, \(i\)-ти од њих је \(a_i\) и он представља моћ \(i\)-тог напитка.

Опис излаза

У првом и једином реду стандардног излаза потребно је исписати један цео број, који представља највећу моћ напитка који може остати у низу након примене свих операција.

Пример 1

Улаз

3 2
5 3 2

Излаз

3

Објашњењe

Миливоје треба да изабере два напитка. Уколико изабере први и последњи напитак и примени другу операцију, он ће добити напитак који има моћ \(a_1-a_3=5-2=3\).

Ограничења

• \(2 \leq K \leq N \leq 200.000\)
• \(|a_i| \leq 100.000\), за свако \(1 \leq i \leq N\)

Тест примери су подељени у пет дисјунктних група:

• У тест примерима вредним \(10\) поена: \(N \leq 10\).
• У тест примерима вредним \(15\) поена: \(N \leq 200\).
• У тест примерима вредним \(20\) поена: \(K = N\).
• У тест примерима вредним \(20\) поена: \(N \leq 1.000\).
• У тест примерима вредним \(35\) поена: Без додатних ограничења.