Star Fruit
InterviewTime limit1sMemory limit256 MB
Given summer length N, growth time T, C plots, and price P, compute the maximum money earnable by planting and replanting each plot as often as possible.
- Level
Easy3 of 10
- Topics
- Greedy, Math, Implementation, Simulation
- Solved
- No attempts yet
Problem
Jinsu grew tired of office life, quit his job, and moved to the countryside to farm crops. Among all the crops, Jinsu likes a crop called 'Star Fruit' the most.
Once a star fruit seed is planted, it takes T days to grow. If a star fruit seed is planted on day i, it can be harvested on day i+T, and a seed can be planted again in the same plot on the day it is harvested.
Jinsu has C empty plots where star fruit seeds can be planted, and each plot holds one star fruit.
Today is summer day 1, and summer lasts until day N. Star fruit withers immediately on any day that is not summer, so no more can be harvested after day N.
Jinsu earns P won for each star fruit he sells. How much money can Jinsu earn during this summer?
Assume Jinsu can work as much as he wants in a day and has enough seeds.
Input
The first line gives the number of summer days N (2 ≤ N ≤ 90), the number of days it takes a star fruit to grow T (1 ≤ T ≤ N-1), the number of plots where star fruit can be planted C (1 ≤ C ≤ 300), and the price per star fruit P (1 ≤ P ≤ 1,000).
Output
On the first line, print the amount of money Jinsu can earn by selling star fruit during the summer.