시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB136553639139.980%

문제

세준이는 잘 모르겠지만, 세준이는 보석에 미쳐있다. 따라서, 숌 보석상에 있는 모든 보석을 다 훔치려고 한다. 하지만, 세준이는 보석을 다 가져올 수는 없다. 그 이유는 가방의 개수에 제한이 있고, 한 가방마다 넣을 수 있는 보석의 개수가 제한이 있기 때문이다. 세준이는 M개의 가방을 가지고 있다. 그리고 각각의 가방은 C그램의 보석을 담을 수 있다.

숌 보석상에는 보석이 N개 있다. N개의 보석의 무게가 주어졌을 때, 세준이가 훔칠 수 있는 보석의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보다 크고, 20보다 작거나 같은 자연수이다. 둘째 줄에 보석의 무게가 하나씩 주어진다. 보석의 무게는 1보다 크거나 같고, 20보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 가져갈 수 있는 최대 보석의 개수를 출력한다.

예제 입력 1

5 2 5
2 2 2 2 2

예제 출력 1

4

예제 입력 2

5 2 5
1 3 5 2 4

예제 출력 2

4

예제 입력 3

4 2 12
7 6 6 5

예제 출력 3

4

예제 입력 4

3 10 1
2 2 2

예제 출력 4

0

출처