Problem G
Island Farming
After a “disagreement” with the captain of your pirate crew, you have been marooned on a barren, deserted island. Unbeknownst to them, there was a hidden cache of $C$ coconuts on this island that you managed to find.
By planting coconuts, you could get enough wood to build a boat and stockpile enough food to take you off the island!
You must meet 2 requirements before you feel comfortable enough to leave the island:
-
A boat, which requires wood from $N$ fully-grown coconut trees.
-
$M$ coconuts to eat on the journey.
The island does not start out with any coconut trees, so you must plant them.
Each day, due to the very rocky ground, you can choose to plant up to one coconut. A coconut tree takes $D$ days to become fully-grown, and once it has grown, it will produce $1$ coconut every day (including one on the day it reaches maturity).
Immature coconut trees do not produce coconuts, and you cannot use them to build your boat. (However, you can build the entire boat on the day that you wish to leave).
Starting from today as day $0$, what is the minimum number of days needed for you to leave the island?
Explanation of Sample Input 1
You start with $C = 5$ coconuts, and you need $N = 2$ coconut trees to build a boat and a stockpile of $M = 6$ coconuts to eat. It takes $D = 2$ days for a coconut tree to grow.
On both day $0$ and day $1$ you plant a coconut, leaving you with $3$ coconuts after day $1$. On day $2$, the first coconut tree matures and produces a coconut, leaving you with $4$ coconuts. On day $3$, the second coconut tree matures and both trees produce a coconut, leaving you with $6$ coconuts.
Since you have $6$ coconuts and $2$ fully-grown coconut trees to build your boat on day $3$, you can leave the island on day $3$.
Input
The only line of input contains four integers $C$, $N$, $M$, and $D$ ($1 \leq C, N, M, D \leq 50$), the number of coconuts you have, the number of coconut trees you need to build a boat, the number of coconuts you need to eat, and the number of days it takes for a coconut tree to grow, respectively.
Output
The soonest day that you can leave the island with a boat built from $N$ fully-grown coconut trees and $M$ coconuts.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 6 2 |
3 |
