보석 모으기
시간 제한2초메모리 제한128 MB
보석 N개의 무게와 가방 M개, 가방당 최대 무게 C가 주어질 때 가방에 담을 수 있는 보석의 최대 개수를 구합니다.
문제
세준이는 M개의 가방을 가지고 있다. 각 가방에는 보석의 총무게가 C그램을 넘지 않도록 여러 개의 보석을 담을 수 있다.
보석 가게에는 N개의 보석이 있고, 각 보석은 한 번만 가져갈 수 있다. 각 보석의 무게가 주어질 때, 세준이가 가방들에 담아 가져갈 수 있는 보석의 최대 개수를 구하라.
입력
첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방 하나가 담을 수 있는 최대 무게 C가 주어진다.
- 1 <= N <= 13
- 1 <= M <= 10
- 1 < C <= 20
둘째 줄에는 N개 보석의 무게가 공백으로 구분되어 주어진다. 각 보석의 무게는 1 이상 20 이하의 자연수이다.
출력
세준이가 가져갈 수 있는 보석의 최대 개수를 출력한다.