스타후르츠
면접 대비시간 제한1초메모리 제한256 MB
여름 길이 N, 성장 기간 T, 밭 개수 C, 가격 P가 주어질 때, 각 밭을 최대한 자주 재배해 벌 수 있는 최대 금액을 구한다.
문제
진수는 회사 생활에 지쳐 회사를 그만두고 귀농해서 작물을 키우며 살고 있다. 진수는 여러 작물 중에서도 '스타후르츠'라는 작물을 가장 좋아한다.
스타후르츠 씨앗을 심으면 자라는 데 T일이 걸린다. i일에 스타후르츠 씨앗을 심으면 i+T일에 수확할 수 있고, 수확한 날에도 같은 칸에 씨앗을 다시 심을 수 있다.
진수에게는 스타후르츠 씨앗을 심을 수 있는 빈 칸이 C개 있고, 한 칸에 스타후르츠 한 개를 심을 수 있다.
오늘은 여름 1일이고 N일까지 여름이 이어진다. 스타후르츠는 여름이 아닌 날에는 곧바로 시들어버리므로 N일이 지나면 더 이상 수확할 수 없다.
진수는 스타후르츠 한 개를 팔면 P원을 번다. 진수는 올해 여름 동안 얼마나 많은 돈을 벌 수 있을까?
진수는 하루에 원하는 만큼 일할 수 있고, 씨앗도 충분히 가지고 있다고 가정한다.
입력
첫 번째 줄에 여름의 일 수 N (2 ≤ N ≤ 90), 스타후르츠가 자라는 데 걸리는 일 수 T (1 ≤ T ≤ N-1), 스타후르츠를 심을 수 있는 칸의 수 C (1 ≤ C ≤ 300), 스타후르츠 개당 가격 정수 P (1 ≤ P ≤ 1,000)가 주어진다.
출력
첫 번째 줄에 진수가 여름 동안 스타후르츠를 팔아 벌 수 있는 수익을 출력한다.