Farmer Bulwęsadź musi obsadzić swoje pola bulwami.</p>

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.</p>

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.

예제 입력

1
9
3

예제 출력

9