Problem description


Zwiększanie wyniku
(I)
Limit pamięci: 32 MB
Limit czasu: 0.25 s

Jak już wiesz z innych zadań, Jasio startuje w zawodach informatycznych i nie idzie mu zbyt dobrze, bo ciągle prosi Cię o pomoc. W ostatnim konteście udało mu się (poprosić kogoś, żeby) złamać zabezpieczenia sprawdzaczki i dzięki temu może sobie powiększyć wynik niektórych zadań. Dokładniej: Jasio może K-krotnie zwiększyć wynik z jakiegoś zadania o 1 punkt. Każde zwiększenie działa w sposób niezależny: Jasio może wszystkie zwiększenia użyć na jednym zadaniu lub jakoś inteligentnie je rozdzielać między zadaniami. Punktacja kontestu jest jednak nieco inna niż zwykle, bo wynik zawodnika to nie suma, a iloczyn wyników poszczególnych zadań. Należałoby teraz jedynie wybrać, gdzie należy zużyć swoje zhackowane zwiększenia, żeby zmaksymalizować ów finalny wynik. Jak się zapewne domyślasz, Jasio będzie miał z tym problem i oczywiście przyszedł po pomoc do Ciebie. Powodzenia!

Napisz program, który wczyta wyniki Jasia oraz wartość K, obliczy maksymalny możliwy do uzyskania finalny wynik Jasia na konteście po zwiększeniach i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz K, oddzielone pojedynczym odstępem. Są to odpowiednio: liczba zadań na konteście oraz maksymalna liczba zwiększeń wyniku zadania (o 1) dostępna dla Jasia. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Są to wyniki Jasia na poszczególnych zadaniach.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – maksymalny możliwy do osiągnięcia iloczyn wyników zadań po wykonaniu zwiększeń.

Uwaga: Możesz założyć, że dane są tak dobrane, że ów wynik nie przekracza 1018.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ K ≤ 109, 0 ≤ Ai ≤ 109.

Przykład

Wejście Wyjście
3 2
2 2 2
18
Wejście Wyjście
5 4
0 0 0 0 0
0
Wejście Wyjście
3 2
0 0 100
100
Wejście Wyjście
4 3
0 100 100 100
3000000