Mali Aleksa je za rođendan od svoje mame dobio niz od ~N~ celih brojeva. Takođe, od tate je dobio ~C~ tokena za aktivaciju čarobne moći. Aleksa može iskoristiti čarobnu moć tako da poveća tačno jedan broj u nizu za 1, i to ga košta 1 token. On može koristiti moć proizvoljno mnogo puta na svakom elementu niza, ali sveukupno ne može iskoristiti moć više od ~C~ puta.

Neka je lepota niza definisana kao suma ~K~-tih stepena svih brojeva u nizu.

Aleksa zna da će ga drugari iz odeljenja ceniti onoliko koliko je lep niz koji on ima. Pomozite Aleksi da maksimizuje lepotu njegovog niza, kao i da izračuna najmanji broj čarobnih moći koje mora da iskoristi kako bi dostigao tu vrednost lepote niza.

Napomena: u ovom zadatku, podrazumevati da je ~0^0 = 0~.

Opis ulaza

U prvoj liniji standardnog ulaza dati su celi brojevi ~N~, ~C~, i ~K~, redom. U sledećoj liniji je dato ~N~ celih brojeva, razdvojenih razmakom, koji predstavljaju elemente niza.

Opis izlaza

U prvoj liniji standardnog izlaza treba ispisati dva cela broja, gde prvi predstavlja maksimalnu dostižnu vrednost lepote niza, a drugi minimalan broj moći koje se moraju iskoristiti kako bi se dostigla ta vrednost.

Primer 1

Ulaz

3 1 2
-5 3 -4

Izlaz

57 1

Primer 2

Ulaz

3 0 0
0 0 0

Izlaz

0 0

Objašnjenje primera

U prvom test primeru, optimalno je da povećamo broj 3 na 4, Rešenje je ~25 + 16 + 16 = 57~.

U drugom test primeru, ~C = 0~, te ne možemo menjati nijedan element niza. Rešenje je ~0 + 0 + 0 = 0~. (videti napomenu)

Ograničenja

U svim podzadacima:

• ~1 \leq N \leq 100.000~
• ~0 \leq C \leq 1.000.000.000~
• Svi elementi niza su po apsolutnoj vrednosti manji ili jednaki ~100.000~
• ~0 \leq K \leq 2~

Test primeri su podeljeni u 3 disjunktne grupe:

• U test primerima vrednim 30 poena: ~N \leq 5~, ~C \leq 5~
• U test primerima vrednim 36 poena: ~N \leq 1000~, ~C \leq 1000~
• U test primerima vrednim 34 poena: Bez dodatnih ograničenja

Napomena

U ovom zadatku, podrazumevati da je ~0^0 = 0~. Ostali stepeni se ponašaju uobičajeno.