33487번 - 대회 운영에 있어 제일 귀찮은 것... 서브태스크스페셜 저지

문제

대회 운영에 있어 제일 귀찮은 것은 에디토리얼 작성 및 편집이지만, 나중에 대회 문제를 업솔빙하거나 풀이가 궁금한 사람들은 에디토리얼이 없다면 참고할 수 있는 수단이 없어 불편할 수 있다. 또한 에디토리얼이 있더라도 특정 대회 혹은 문제의 에디토리얼을 찾는 것은 쉽지 않을 수 있다. 이에 유틸은 CP(Competitive Programming) 대회들의 에디토리얼을 모아둔 GitHub 레포지토리를 만들어 정리해 많은 PS(Problem Solving)러들에게 도움을 주고자 한다.

이 소식을 들은 동우는 본인의 게으름을 반성하며 6회 MatKor Cup이 끝나고 여유가 생기면 이제는 진짜로 4회 대회부터 공개되지 않은 에디토리얼을 이번 대회까지 포함해 모두 작성, 편집해 유틸의 레포지토리에 공유하고자 한다. 이를 위해 동우는 에디토리얼 문서 작성을 해야 한다.

문서 작성을 위해 동우가 사용하는 프로그램의 한 줄의 길이는 $L$이며, 공백으로 구분된 몇 개의 단어로 이루어진 문서를 작성하려고 한다. 양쪽 정렬을 사용할 시 다음과 같이 정렬되며, 각 줄의 공백은 다음과 같이 정의된다.

• 서로 다른 단어는 다른 줄에 위치하거나, 같은 줄의 경우 단어 간 최소 1ドル$ 이상의 간격이 필요하다.
• 한 단어는 같은 줄에 모두 포함되어야 한다. 즉, 한 단어를 다음 줄로 넘기지 못한다.
• 아래 “마지막 줄이 아닐 때” “한 줄에 한 개의 단어만 포함할 경우”를 제외하고는, 같은 단어 내의 글자는 공백없이 붙여 쓴다.
• 한 줄에 들어갈 단어가 결정될 경우 다음과 같이 문서가 작성된다. 모든 경우에 대해 그 줄의 길이를 초과해 단어를 적을 수는 없다.
  • 마지막 줄이 아닐 때
    • 한 줄에 두 개 이상의 단어를 포함할 경우 첫 글자와 마지막 글자를 그 줄의 가장 앞과 뒤로 맞춘 뒤, 단어 간 공백을 균등하게 나눈다. 즉, 정수 $n\ge 2$에 대해 한 줄에 길이가 $s_1,s_2,\cdots ,s_n$인 단어를 적고 싶다면, 그 줄의 공백의 크기는 $\frac{L-\sum_i{s_i}}{n-1}$이며, 1ドル$ 이상이어야 한다.
    • 한 줄에 한 개의 단어만 포함할 경우 첫 글자와 마지막 글자를 그 줄의 가장 앞과 뒤로 맞춘 뒤, 글자 간 간격을 균등하게 나눈다. 즉, 그 한 줄에 길이가 $s$인 단어 하나만 적고 싶다면, 그 줄의 공백의 크기는 $\frac{L-s}{s-1}$이다. 다만, 그 단어의 길이가 1ドル$인 경우에는 첫 글자를 그 줄의 가장 앞으로 맞춘 뒤 그 뒤로 $L-1$만큼의 공백이 생긴다.
  • 마지막 줄일 때
    • 한 줄에 두 개 이상의 단어를 포함할 경우 첫 글자를 그 줄의 가장 앞으로 맞춘 뒤, 단어 간 공백을 1ドル$로 하여 나머지 단어를 적는다. 즉, 그 줄의 공백의 크기는 1ドル$이 된다.
    • 한 줄에 한 개의 단어만 포함할 경우 첫 글자를 그 줄의 가장 앞으로 맞춘 뒤, 공백 없이 적는다. 즉, 그 줄의 공백의 크기는 0ドル$이 된다.

동우는 문서를 작성할 때, 각 줄의 공백의 최댓값이 최소가 되도록, 만약 그런 경우가 여러 가지일 경우 총 줄의 수가 최소가 되도록 하고 싶다. 동우가 작성할 $N$개의 단어의 $W_1,W_2,\cdots ,W_N$의 길이 $a_1,a_2,\cdots ,a_N$과 $L$이 주어진다.

단어 $W_1,\cdots ,W_N$을 차례로 작성할 때 각 줄의 공백의 최댓값이 최소가 되도록 해보자.

입력

첫 번째 줄에 단어의 개수 $N(1\le N\le 10^6),ドル $L(1\le L\le 10^{9})$이 공백으로 구분되어 주어진다.

두 번째 줄에 각 단어의 길이 $a_1,a_2,\cdots ,a_N(1\le a_i\le L)$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 단어 $W_1,\cdots ,W_N$을 차례로 작성할 때 각 줄의 공백의 최댓값의 최솟값 $z$를 출력한다.

출력한 값이 정답과 절대/상대 오차가 10ドル^{-9}$ 이하라면 정답으로 한다.

제한

서브태스크

힌트