시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 256 MB 1291 245 (19%) 190
문제
유치원 교사인 정우는 매일 $N$명의 어린이들에게 선물을 준다. 오늘은 어떤 선물을 줄지 생각하던 정우는 머리에 리본을 하나씩 달아주려고 한다. 리본을 만들기 위해 끈을 찾았는데, $K$개밖에 없는 것이다$(K \le N)$. 따라서 어쩔 수 없이 리본끈을 잘라서 사용해야 한다. 정우반 아이들은 까다롭기 때문에 다음과 같은 규칙으로 리본이 있어야 울지 않는다. * 모든 어린이들의 리본끈 길이는 같아야 한다. (어린이들이라 질투를 느낀다.) * 리본끈의 길이는 정수이다. (아직 소수를 배우지 않아 정수밖에 모든다.) * 리본끈에 이음새가 있으면 안된다. 즉, 리본끈 두개를 이어붙이면 안된다. 길이가 제각각인 $K$개의 리본끈을 갖고, 길이가 모두 같은 $N$개의 끈을 만들어야 한다. 리본을 이쁘게 만들려면 최대한 리본끈이 길면 좋다. 따라서 이렇게 만들 수 있는 리본끈의 길이 중 최대의 길이로 자를 것이다. 정우를 도와 최대의 리본끈 길이를 찾으시오.
입력
첫째 줄에는 갖고 있는 리본끈의 개수 K와, 어린이의 수 N이 입력된다$(1 \le K \le 10,000, 1 \le N \le 1,000,000, K \le N)$. 그리고 그 다음 K줄에 걸쳐서 갖고있는 리본끈의 길이가 주어진다. 리본끈의 길이는 $2^{31}-1$보다 작거나 같은 자연수이다.
출력
첫째 줄에 만들 수 있는 리본끈의 길이 중, 최대값을 출력하시오.
힌트
### 입력 예제 ### ``` 4 13 100 310 505 409 ``` ### 출력 예제 ### ``` 100 ``` ### 예제 설명 ### 길이가 $50$이 되게 리본끈을 만들면, 각각의 갖고있는 리본끈에 대해서 $2$개, $6$개, $10$개, $8$개를 만들 수 있고, 합치면 총 $26$개를 만들 수 있다. 따라서 모든 아이들에게 조건에 맞는 리본끈을 선물해줄 수 있다. 또한 길이가 $100$인 경우에도, 각각 $1$개, $3$개, $5$개, $4$개를 만들어서, 총 $13$개의 리본을 만들 수 있다. 이 경우에도 모든 아이들에게 리본을 선물해줄 수 있다. 하지만 길이가 101인 경우에는, 각각 0개, 3개, 5개, 4개를 만들어서, 총 12개의 리본밖에 만들지 못한다. 따라서 이 경우는 모든 아이들에게 리본을 선물할 수 없다. 따라서 가능한 길이 중 최대값은 100이 된다.