8692번 - Sadzenie bulw 다국어

문제

Farmer Bulwęsadź musi obsadzić swoje pola bulwami.

Każde pole ma określoną bulwonasyconość wyrażającą się liczbą całkowitą b_i. Jeżeli zasadzi się na tym polu k bulw, gdzie 0 ≤ k ≤ b_i, to plon wyniesie k². Jeżeli zasadzi się na tym polu więcej niż b_i bulw, to plonu nie będzie ze względu na wzajemne zagłuszanie.

Farmer nie za dobrze radzi sobie z matematyką, a ma ograniczony zasób bulw. Powiedz mu, jak ma zasadzić swoje bulwy, żeby osiągnąć maksymalny plon. Zakładamy, że farmer nie musi zasadzać wszystkich bulw.

입력

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁵), oznaczającą liczbę pól Bulwęsadzia.

Następny wiersz zawiera n liczb całkowitych b₁, b₂, ..., b_n (0 ≤ b_i ≤ 10⁴), gdzie b_i oznacza bulwonasyconość i-tego pola. Ostatni wiersz zawiera jedną liczbę całkowitą m (1 ≤ m ≤ 10¹⁰), oznaczającą liczbę bulw, które posiada Bulwęsadź.

출력

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita, oznaczająca maksymalny łączny plon Bulwysadzia.

제한

힌트