포도 수확하기 1

문제 배경

입장포도는 충청남도 천안시 서북구 입장면에서 재배되는 지역 특산물이다. 비옥한 토양과 적합한 기후 조건에서 자라기 때문에 크기가 크고 과육이 풍부하며 당도가 높다.

문제

n그루의 포도나무가 있다. 각 나무 i에는 ci개의 포도가 달려 있다. 상자 한 개에는 같은 나무의 포도만 담을 수 있고, 최대 m개까지 넣을 수 있다. k개의 상자를 사용할 수 있을 때, 최대 몇 개의 포도를 판매할 수 있는지 구하시오.