더 빠르게 타이핑하기

이미지 출처: 2024.nwerc.eu

프로그래밍 대회에서는 빠르게 타이핑하는 것이 유용할 때가 많다. 특히 시간 페널티로 인해 순위표에서 여러 순위가 오르내릴 수 있을 때는 더욱 그렇다. 이제 당신은 이전 대회에서 우승하려면 어느 정도가 필요했을지 궁금해졌다.

당신은 상당히 낙관적이어서 모든 문제를 첫 시도에 해결한다고 가정한다. 따라서 각 문제의 첫 제출에 대해서만 시간 페널티를 받는다. 대회의 최고 팀은 모든 문제를 해결했으므로, 당신도 똑같이 모든 문제를 해결하고 그 팀의 시간 페널티를 이겨야 한다. 또한 최고 팀의 시간 페널티를 이겨야 한다는 조건 외에는 대회에 시간제한이 없다고 가정하자. 그 팀의 시간 페널티와 같기만 해서는 충분하지 않으며, 당신의 시간 페널티가 반드시 그보다 엄격히 작아야 한다.

$x$분에 풀이를 제출하면 값 $x$이 시간 페널티에 더해진다. 즉, $1$분 $59$초에 제출한 풀이의 시간 페널티는 $1$이지만, $2$분 후에 제출한 풀이의 시간 페널티는 $2$이다.

따라서 분당 $20$단어를 타이핑할 수 있고 풀이가 $100$단어로 이루어져 있으며 그 문제를 먼저 풀기 시작한다면, 시간 페널티는 $5$이 된다. 하지만 풀이가 $99$단어라면 시간 페널티는 $4$이 된다.

당신은 머릿속으로 모든 문제의 풀이를 알아냈으며 각 문제의 풀이가 정확히 몇 단어인지 알고 있다. 하지만 최고 팀을 이길 만큼 빠르게 타이핑할 수 있을지는 확신하지 못한다. 따라서 질문은 다음과 같다. 최고 팀을 이기려면 분당 몇 단어를 타이핑해야 하는가?

채점

그룹 | 점수 | 제약 조건

1 | 10 | $n = 1$.

2 | 15 | $T = 1$.

3 | 25 | $n \leq 100, \sum_{i=0}^n w_i \leq 1\,000$

4 | 50 | 추가 제약 조건이 없다.

입력의 첫째 줄에 두 정수 $n, T$가 주어진다. $n$은 대회에서 당신이 풀어야 하는 문제의 수이고, $T$는 당신이 이겨야 하는 최고 팀의 시간 페널티이다. 항상 $1 \leq n \leq 100\,000$ 및 $1 \leq T \leq 10^{18}$가 성립한다. 입력의 둘째 줄이자 마지막 줄에 $n$개의 정수 $w_1, w_2, \dots, w_n$가 주어진다. $w_i$은 $i$번째 문제 풀이의 단어 수이다. 모든 $i$에 대해 항상 $0 \leq w_i \leq 10^9$가 성립한다. 모든 $w_i$의 합은 $0$가 아닐 것이다.

최고 팀을 이기는 데 필요한 가장 낮은 분당 단어 수를 출력한다.