27991번 - 고장난 프린터

문제

프린터 기기는 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 민수가 사용하는 프린터는 $N$개의 인쇄 요청을 받았고, 프린터가 가진 초기 잉크 용량은 $M$이다. 인쇄 시작 버튼을 누르면 인쇄 요청을 받은 순서로 1번째 문서, 2번째 문서, ..., $N$번째 문서를 인쇄한다.

$x_i$는 $i$번째 문서를 품질이 좋게 인쇄하기 위해 필요한 최소 잉크의 양을 의미한다. $i$번째 문서를 인쇄할 때 $x_i$보다 적은 잉크의 양을 사용한다면, $i$번째 문서의 인쇄물은 품질이 좋지 않다. 반대로 $x_i$보다 같거나 많은 잉크를 사용하여 인쇄하면, $i$번째 문서의 인쇄물은 품질이 좋다.

그런데 프린터가 고장 나서 각 문서를 인쇄할 때 항상 잉크를 $K$만큼 사용한다. 따라서 각 문서를 인쇄할 때마다 잉크 잔량은 $K$씩 줄어든다. 만약 $i$번째 문서를 인쇄할 때 잉크 잔량이 $K$보다 작다면 남은 잉크를 모두 사용하여 문서를 인쇄하고, 잉크 잔량은 0ドル$이 된다.

다행히 민수가 이 $K$를 음이 아닌 정수로 직접 정할 수 있다. 인쇄 시작 버튼을 눌렀을 때 최대한 많은 문서를 품질이 좋게 인쇄하고 싶다. 민수를 도와 이러한 $K$의 최솟값을 구해주자.

입력

첫 번째 줄에 프린터가 받은 인쇄 요청의 개수 $N,ドル 프린터의 초기 잉크 용량을 나타내는 정수 $M$이 주어진다.

두 번째 줄에 각 문서를 품질이 좋게 인쇄하기 위해 필요한 최소 잉크의 양을 나타내는 정수 $x_1, x_2, x_3, \cdots, x_N$이 주어진다.

출력

최대한 많은 문서를 품질이 좋게 인쇄하기 위한 음이 아닌 정수 $K$의 최솟값을 출력한다.

제한

• 1ドル \le N \le 10^6$
• 1ドル \le M, x_i \le 10^{12}$

힌트