감자 심기

면접 대비

시간 제한1초메모리 제한128 MB

요약

상한 b_i가 있는 밭들에 최대 m개의 감자를 나누어 심어 개수 제곱합이 가장 커지도록 합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

한 농부가 여러 밭에 감자를 심으려고 합니다.

각 밭 $i$ 에는 정수로 주어지는 포화도 $b_i$ 가 있습니다. 어떤 밭에 감자를 $k$ 개 심고 $0 \le k \le b_i$ 이면 그 밭의 수확량은 $k^2$ 입니다. 만약 $b_i$ 개보다 많이 심으면 포기들이 서로 방해하여 그 밭에서는 수확량이 전혀 나오지 않습니다.

농부가 가진 감자의 수는 정해져 있으며, 가진 감자를 모두 심을 필요는 없습니다. 얻을 수 있는 전체 수확량의 최댓값을 구하세요.

입력

첫째 줄에 밭의 개수 $n$ ( $1 \le n \le 10^5$ )이 주어집니다.

둘째 줄에 $n$ 개의 정수 $b_1, b_2, \ldots, b_n$ ( $0 \le b_i \le 10^4$ )이 주어지며, $b_i$ 는 $i$ 번째 밭의 포화도입니다.

셋째 줄에 농부가 가진 감자의 수 $m$ ( $1 \le m \le 10^{10}$ )이 주어집니다.

출력

전체 수확량의 최댓값을 한 줄에 정수 하나로 출력합니다.

예제4

예제 1
입력
```
1
9
3
```
예상 출력
```
9
```
예제 2
입력
```
3
2 3 4
100
```
예상 출력
```
29
```
예제 3
입력
```
2
3 3
4
```
예상 출력
```
10
```
예제 4
입력
```
5
1 2 3 4 5
7
```
예상 출력
```
29
```