시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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

Każde pole ma określoną bulwonasyconość wyrażającą się liczbą całkowitą bi. Jeżeli zasadzi się na tym polu k bulw, gdzie 0 ≤ kbi, to plon wyniesie k2. Jeżeli zasadzi się na tym polu więcej niż bi 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 ≤ 105), oznaczającą liczbę pól Bulwęsadzia.

Następny wiersz zawiera n liczb całkowitych b1, b2, ..., bn (0 ≤ bi ≤ 104), gdzie bi oznacza bulwonasyconość i-tego pola. Ostatni wiersz zawiera jedną liczbę całkowitą m (1 ≤ m ≤ 1010), 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

1
9
3

예제 출력 1

9