시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15 2 2 50.000%

문제

오세준은 세계 정복을 위해 전 세계에 있는 N개의 국가를 정복했다. 세준이는 N개의 국가에 있는 사람들이 서로 친하지 않음을 깨닫고 세계 정복을 위해서라면 모든 사람들을 서로 친하게 만들어야 한다는 것을 알았다.

세준이는 전세계의 사람들을 그룹으로 나누려고 한다. 그룹을 나누는 방법에는 다음과 같은 조건이 있는데, 첫 번째는 그룹에 들어있는 사람의 수는 정확히 K명이어야 한다. 또, 각 그룹에 있는 사람들은 모두 다른 나라 소속이어야 한다는 것이다.

세준이는 N개의 국가에 살고 있는 사람의 수가 주어졌을 때, 이 사람들을 최대 몇 개의 그룹으로 나눌 수 있는지 궁금해졌다.

예를 들어, 중국에 살고 있는 사람이 4명, 캐나다에 살고 있는 사람이 4명, 폴란드, 스웨덴, 미국에 살고 있는 사람이 모두 4명이고, K가 4라면, 세준이는 최대 5개의 그룹으로 나눌 수 있다.

캐나다, 중국, 폴란드, 스웨덴
캐나다, 중국, 폴란드, 미국
캐나다, 중국, 스웨덴, 미국
캐나다, 폴란드, 스웨덴, 미국
중국, 폴란드, 스웨덴, 미국

만약 어느 그룹에도 들어가지 않는 사람이 있다면, 세준이는 이 사람들을 과감히 무시한다.
 

입력

첫째 줄에 국가의 수 N과 K가 주어진다. N은 K보다 크거나 같고, 100보다 작거나 같은 자연수이고, K는 20보다 작거나 같은 자연수이다. 둘째 줄에는 각 나라에 살고 있는 사람의 수가 공백으로 구분해서 차례대로 주어진다. 이 수는 1000000000보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 출력한다. 정답은 2^63-1보다 작거나 같다.

예제 입력

5 4
4 4 4 4 4

예제 출력

5

힌트

출처