해저 탐사

문제

해양 탐사 다이버 성민이는 마리아나 해구의 미개척 해저 구간을 조사하는 임무를 맡았다. 조사할 구간에는 $1$번부터 $N$번까지 일렬로 이어진 탐사 지점이 있으며, $i$번 지점의 해저 수심은 $h_i$밀리미터이다.

성민이는 탐사를 시작하기 전에 목표 잠수 수심을 음이 아닌 정수 $D$밀리미터로 정한다. 이후 $1$번 지점부터 $N$번 지점까지 차례로 이동한다. 해저보다 깊이 내려갈 수는 없으므로, $i$번 지점에서 실제로 잠수하는 수심은 $d_i = \min(h_i, D)$이다.

성민이가 안전하게 탐사를 마치려면 다음 두 조건을 모두 만족해야 한다.

1. 공기 소모 한계: $i$번 지점에서 $d_i$만큼의 공기를 소모한다. 모든 지점에서 소모한 공기량의 합은 공기통 용량 $A$를 넘을 수 없다.
2. 질소 부하 한계: $i$번 지점에서 $d_i^2$만큼의 질소 부하가 누적된다. 모든 지점에서 누적된 질소 부하의 합은 안전 한계치 $M$을 넘을 수 없다.

즉, $\sum_{i=1}^{N} d_i \le A$와 $\sum_{i=1}^{N} d_i^2 \le M$을 모두 만족해야 한다.

성민이가 두 안전 조건을 지키며 탐사할 수 있는 목표 잠수 수심 $D$의 최댓값을 구해 보자. 가능한 $D$에 상한이 없다면 $-1$을 출력한다.

입력

첫째 줄에 탐사 지점의 수 $N$, 공기통 용량 $A$, 질소 부하 한계치 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 200,000; 0 \le A \le 2 \times 10^{12}; 0 \le M \le 10^{18})$

둘째 줄에 각 지점의 해저 깊이를 나타내는 $N$개의 정수 $h_1, h_2, \ldots, h_N$이 공백으로 구분되어 주어진다. $(0 \le h_i \le 10,000,000)$

출력

공기 소모 한계와 질소 부하 한계를 모두 만족하는 목표 잠수 수심 $D$의 최댓값을 출력한다.

가능한 $D$에 상한이 없다면 $-1$을 출력한다.

예제 1

4 13 47
2 5 8 10

출력 1

3