Zadanie

Elitárska hostina

Počet bodov: 35

Na celoštátnom kole istej súťaže v programovaní býva večer recepcia pre pedagogický dozor a organizátorov. Je tam množstvo nápojov, živý kuchár, ba dokonca dlhočizný rad nádob so všakovakými pochutinami, kde v \(i\)-tej nádobe je jedlo o hmotnosti \(m_i\).

Smutní účastníci sa počas recepcie nudia a sú hladní. Niet preto divu, že sa niektorí z nich rozhodli pokúsiť sa prepašovať dnu.

Maťko bol so svojim mladíckym vzhľadom odhalený a zastavený hneď pri vstupe pri pokuse o zisk pohára bublinkového vína. Krtko sa však zvládol tváriť dostatočne nenápadne a skúsene.

Neváhal a okamžite zamieril k bufetu. Len čo sa bezhlavo začal naťahovať za chrumkavou kroketou, uvedomil si, že by vzbudil priveľkú pozornosť, keby všetko dostupné jedlo skonzumoval. Bolo by však zvláštne aj to, keby nič nezjedol. A tiež keby zbesilo pobehoval medzi rôznymi časťami bufetu.

Rozhodol sa preto, že skonzumuje potravu zo súvislého úseku nádob. Keď už nejakú nádobu načne, úplne ju vyprázdni (inú možnosť ani nemá, keď začne, nevie sa ovládať). Naviac, celková hmotnosť jedla skonzumovaná Krtkom je \(k\)-ta najmenšia zo všetkých možných.

Vstup

V prvom riadku vstupu sú čísla \(n\) – počet nádob s jedlom a \(k\).

Na ďalšom riadku je \(n\) medzerou oddelených čísiel \(m_1,\ ...,\ m_n\) – hmotnosti jedla v jednotlivých nádobách tak, ako sú uložené vedľa seba. Platí \(0 \leq m_i \leq 10^9\)

Platí \(1 \leq n\). Taktiež platí \(1 \leq k \leq \frac{n(n + 1)}{2}\). Naviac platí, že v jednotlivých sadách je \(n\) najviac postupne \(1\,000\), \(30\,000\), \(30\,000\) a \(k\) je najviac postupne \(500\,500\), \(1\,000\), \(450\,015\,000\).

Výstup

Na jediný riadok výstupu vypíšte jedno číslo – \(k\)-ty najmenší súčet súvislého úseku hmotností jedál v nádobách.

Príklady

Input:

5 3
5 4 3 2 1

Output:

3

Súčty súvislých úsekov sú 1, 2, 3, 3, 4, 5, 5, 6, 7, 9, 9, 10, 12, 14, 15, Z nich je tretí najmenší 3.