Кенжекей Ер-Төстікке \(n\) тәтті пирог жасап берді. \(i\)-ші пирогтың тәттілігі \(a_i\). Енді пирогтарға Ер-Төстіктің қауіп-қатерлі әрекеттерінде керек болатын \(k\) сиқырлы қоспаны қосу ғана қалды. Әрбір қоспа пирогтың тәттілігін \(1\)-ге арттырады және бір пирогқа бірнеше қоспалар қосуға болады.

Кенжекей Ер-Төстіктің нағыз батыр екенің біледі, сол себепті оның барлық \(n\) пирогқа шамасы шетеді. Ішке түскенде пирогтардың тәттілігі көбейтіліп кетеді; осылайша пирогтардың жалпы тәттілігі келесі формуламен саналады \[\sum_{(i,j): 1 \le i < j \le n} a_i \cdot a_j,\] мұндағы қосынды барлық жұп пирогтарды қарастырады. Кенжекей Ер-Төстіктің жақында жолға шығатынын біледі, және тәтті жеген сайын жолын бастау қиынға соғатынын да түсінеді. Ол барлық пирогтардың жалпы тәттілігін азайтуды қалайды.

Оған қоспаларды ең оңтайлы түрде косуға көмектесіңіз.

Input

Бірінші жолда екі бүтін сан \((1 \le n \le 10^5, 0 \le k \le 10^9)\) — пирогтардың саны және қоспалардың саны.

Екінші жолда \(n\) бүтін сан \(a_1,\ldots,a_n\) \((0 \le a_i \le 10^4)\) — әр пирогтың тәттілігі.

Output

\(k\) қоспаларын қосқаннан кейін пирогтардың ең аз жалпы тәттілігін шығарыңыз.

Sample Input 1

4 0
0 1 2 3

Sample Output 1

11

Sample Input 2

5 20
12 7 10 11 1

Sample Output 2

1213

Notes

Бірінші мысалда ешқандай қоспалар жоқ, енді пирогтардың жалпы тәттілігі: \((0 \cdot 1 + 0 \cdot 2 + 0 \cdot 3) + (1 \cdot 2 + 1 \cdot 3) + 2 \cdot 3 = 0 + 5 + 6 = 11\).