Bogdan's Apple Store
Limits: 2 sec., 256 MiB
Bogdan’s favorite fruit is apple. But he likes them not for the delicious taste but for the money he’s making out of them. He was distributing apples in a well-known Lviv company for years. He has an infinite amount of apples at home because he knows how to steal them.
Bogdan, tired from distributing apples, decided to start his own business by selling apples. He already bought a table which is \(n\) units long and \(m\) units wide. Now he needs to display as many apples on it as possible. He can either put an apple directly on the table, taking one square unit of area, or put a box on the table, taking \(k\times k\) units of space and put \(x\) apples inside. It is not allowed by federal law to stuck boxes or apples that are not in the box on top of each other.
His friend Volodymyr, who works in the woodshop, can steal boxes from his factory. Having an infinite amount of boxes, what is the maximum number of apples Bogdan can put on the table?
Input
Four integers \(n\), \(m\), \(k\), and \(x\) in one line.
Output
One integer – answer to the question.
Constraints
\(1 \le n, m \le 10^{8}\),
\(1 \le k \le 100\),
\(1 \le x \le 100\).
Samples
Input (stdin) | Output (stdout) |
---|---|
5 4 2 5 | 24 |
Input (stdin) | Output (stdout) |
---|---|
5 4 5 100 | 20 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|