투표함 나누기

오늘 SWERC'11 외에도 스페인에서는 그에 못지않게 중요한 또 하나의 큰 행사가 열립니다. 바로 총선입니다. 만 18세 이상의 이 나라 모든 주민은 하원(대의원회)과 상원의 대표를 뽑기 위해 투표하도록 요청받습니다. 투표는 의무가 아니니, 모든 심사위원이 갑자기 감독 임무를 내팽개칠까 봐 걱정하지 않아도 됩니다.

행정 당국에는 지난 선거에서 쓰던 투표함이 여러 개 있습니다. 안타깝게도 도시들에 투표함을 분배하던 담당자가 몇 달 전 예산 삭감으로 해고되었습니다. 그 결과, 현재의 투표함-도시 배정과 각 투표함에서 투표할 사람들의 명단은 최선이라고 보기 어렵습니다. 이 일을 얼마나 효율적으로 할 수 있었는지 보여 주는 것이 여러분의 과제입니다.

투표함을 도시에 배정할 때의 유일한 규칙은 모든 도시가 적어도 하나의 투표함을 받아야 한다는 것입니다. 각 사람은 자신에게 배정된 투표함에서 투표합니다. 여러분의 목표는 하나의 투표함에 배정되어 투표하는 사람 수의 최댓값을 최소화하는 분배를 찾는 것입니다.

첫 번째 예제에서는 첫 번째 도시에 투표함 2개, 나머지가 두 번째 도시에 가고, 가장 효율적인 분배에서는 (거대한!) 각 투표함에 정확히 100000명이 배정됩니다. 두 번째 예제에서는 도시들이 각각 투표함 1, 2, 2, 1개를 받고, 세 번째 도시의 1700명이 그 도시의 두 투표함 각각에서 투표하게 되어, 최적 배정에서 이 투표함들이 가장 붐비게 됩니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$($1 \le N \le 500000$, 도시의 수)과 $B$($N \le B \le 2000000$, 투표함의 수)가 주어집니다. 이어지는 $N$개의 줄에는 각각 정수 $a_i$($1 \le a_i \le 5000000$)가 주어지며, 이는 $i$번째 도시의 인구입니다.

각 테스트 케이스 뒤에는 빈 줄이 하나씩 옵니다. 입력의 마지막 줄에는 -1 -1이 주어지며 처리하지 않습니다.

각 테스트 케이스에 대해, 가장 효율적인 배정에서 한 투표함에 배정된 사람 수의 최댓값을 정수 하나로 출력하세요.