사진 캡션

UCF 프로그래밍 팀 연구실(PTL)은 HEC에 있다. 연구실 밖에는 팀 사진이 게시된다. 사진 캡션을 작성할 때는 사진 아래 각 줄에 이름을 몇 개씩 적을지 정해야 한다.

이름의 개수, 캡션에 사용할 줄 수, 각 이름의 글자 수가 주어졌을 때, 캡션에서 가장 긴 줄의 길이를 최소화하라.

이름은 입력 순서대로 캡션에 나와야 한다. 순서를 바꿀 수 없다. 다음 조건도 지켜야 한다.

• 각 줄의 첫 번째 이름 앞에는 공백이 없다.
• 각 줄의 마지막 이름 뒤에는 공백이 없다.
• 각 줄에서 연속한 두 이름 사이에는 공백이 정확히 하나 있다.

첫 번째 줄에 이름의 개수 $n$과 캡션에 사용할 줄 수 $k$가 정수로 주어진다 ($1 \le k \le n \le 10^5$).

두 번째 줄에는 각 이름의 글자 수 $c_i$가 순서대로 $n$개의 정수로 주어진다 ($1 \le c_i \le 10^4$).

가장 긴 줄의 길이를 최소화했을 때, 그 길이를 출력한다.