Do it!

Time limit1sMemory limit128 MB

Summary

Choose when to shout 'do it!' over time so that positive, negative, and neutral workers finish their 100-unit fixtures with the smallest total finish time.

Level: Medium7 of 10
Topics: Greedy, Math, Brute force, Implementation
Solved: No attempts yet

Problem

You are the boss of a small lighting-fixture company with $n$ employees. Whenever you want something done, you have taken up the habit of shouting "do it!" over the company intercom. Of your employees, $n_+$ respond positively to your "do it!", $n_-$ respond negatively, and $n_0$ are unaffected.

At time $0$ , every employee starts building their own lighting fixture. Each fixture requires $100$ units of labor to finish. Normally, each employee contributes $r$ units of labor per unit of time (or the amount of labor remaining, whichever is smaller), so an employee normally takes $\lceil 100/r \rceil$ units of time to finish a fixture.

During any unit of time, however, if you shout "do it!" over the intercom, then during that unit of time an employee who responds positively does $r+2$ units of labor, while one who responds negatively does $r-1$ units of labor. An unaffected employee always does $r$ units of labor.

Each employee works only on their own fixture, and you may shout "do it!" at most once per unit of time. Your goal is to plan a sequence of "do it!"s so that the sum, over all $n$ fixtures, of the times needed to finish them is minimized.

Input

The input consists of several test cases. Each test case is a single line containing four integers $n_+$ , $n_-$ , $n_0$ , and $r$ ( $0 \le n_+, n_-, n_0 \le 1000$ and $1 \le r \le 100$ ). The end of input is marked by a line with $n_+ = n_- = n_0 = r = 0$ , which must not be processed.

Output

For each test case, print on its own line the minimum possible sum of the times needed to finish all $n$ fixtures.

Hint

In the first example $(3\ 1\ 1\ 2)$ , one optimal strategy is to shout "do it!" during each of the first $25$ units of time. The $3$ positively-responding employees then contribute $4$ units of labor per unit of time and finish in $25$ units of time. The $1$ negatively-responding employee contributes $1$ unit of labor per unit of time for the first $25$ units of time and $2$ afterwards, finishing at $25 + 38 = 63$ . The unaffected employee always contributes $2$ units of labor and finishes at $50$ . This gives a total of $3 \times 25 + 63 + 50 = 188$ .

In the second example $(1\ 3\ 0\ 2)$ , an optimal strategy is to never shout "do it!". All four employees then finish at $50$ , for a total of $200$ .

Examples1

Example 1
Input
```
3 1 1 2
1 3 0 2
0 0 0 0
```
Expected output
```
188
200
```