세탁소의 포장 완료 시각

문제

세탁소에서는 세탁과 건조를 끝낸 수건을 같은 크기의 묶음으로 포장하고 있다. 오늘 사용할 자동 포장기는 N대이며, 각 포장기가 수건 한 묶음을 포장하는 데 걸리는 시간은 정수 분으로 정해져 있다. 포장기마다 작업 속도는 다를 수 있지만, 한 포장기의 작업 시간은 하루 동안 바뀌지 않는다. 모든 포장기는 시각 0에 첫 묶음의 포장을 시작한다. 포장기 i가 한 묶음을 포장하는 데 A_i분이 걸린다면, 그 포장기는 시각 A_i에 첫 묶음을 완성한다. 완성한 묶음은 즉시 옆의 보관대에 놓이고, 포장기는 쉬지 않고 다음 묶음의 작업을 시작한다. 따라서 같은 포장기의 두 번째 묶음은 시각 2A_i에 완성된다. 작업을 시작했지만 아직 포장이 끝나지 않은 묶음은 완성된 수에 포함하지 않는다. 정확히 어떤 시각에 작업이 끝났다면 그 시각부터 완성된 묶음으로 센다. 수건과 포장 재료는 충분히 준비되어 있으며, 포장기끼리 재료를 기다리거나 서로의 작업을 방해하는 일은 없다. 완성된 묶음은 포장기에 관계없이 모두 같은 용도로 사용할 수 있다. 또한 여러 포장기가 같은 시각에 작업을 끝내면 그 묶음들을 모두 함께 센다. 보관대의 크기에도 제한은 없다. 세탁소는 완성된 묶음이 K개 이상 모이는 즉시 배송 준비를 시작하려고 한다. 시각 0 이후 몇 분이 지나야 처음으로 이 조건을 만족하는지 구하는 프로그램을 작성한다. 답은 경과한 시간을 나타내는 0 이상의 정수로 출력한다. 필요한 수를 넘는 묶음이 한꺼번에 완성되어도 괜찮다. 포장기는 적어도 한 대이고 모든 작업 시간이 양수이므로 배송 준비를 시작할 수 있는 시각은 반드시 존재한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1≤N≤100,000이고 1≤K≤1,000,000,000이다.
둘째 줄에 N개 포장기의 작업 시간 A_1, …, A_N이 공백으로 주어진다. 모든 A_i는 정수이며 1≤A_i≤9이다.

출력

완성된 묶음이 처음으로 K개 이상이 되는 시각을 정수 하나로 출력한다. 단위는 분이며 단위 문자는 출력하지 않는다.

3 8
2 3 5

9

4 3
7 7 7 7

7

1 4
9

36

출처: Devin.KR 자체 제작