Description

You are the boss of a small lighting fixture company which has n employees. Inspired by Ben Stiller’s character in Starsky and Hutch, you have recently taken on the habit of telling your employees to “do it!” when you want things done. While n₊ of the n employees respond positively to your “do it!”s, n₋ employees respond negatively and n₀ are neutral to your words.

At time 0, each of your employees begins working alone on building a lighting fixture. Each lighting fixture takes 100 units of labor to finish. Normally, each of your employees contributes r units of labor towards finishing his/her lighting fixture during each time interval (or the amount of labor units remaining for the fixture, whichever is smaller). Thus, an employee would normally take ceiling(100 ⁄ r) time intervals to finish his or her lighting fixture. During an interval, however, if you yell “do it!” over the company intercom, employees who respond positively to your command will do r + 2 units of labor during that time interval, whereas employees who respond negatively will do r − 1 units of labor during the time interval.

Assuming that each employee works on only his or her lighting fixture, and assuming that you yell “do it!” at most once during each time interval, your goal is to plan a sequence of “do it!”s so as to ensure that the sum of the times needed to finish all n lighting fixtures is minimized.

Input

The input test file will contain multiple test cases. Each input test case will be given as a line containing four integers, n₊, n₋, n₀, and r (where 0 ≤ n₊, n₋, n₀ ≤ 1000 and 1 ≤ r ≤ 100). The end-of-file is marked by a test case with n₊ = n₋ = n₀ = r = 0 and should not be processed.

Output

For each input case, the program should print the minimum sum of times needed to finish all n lighting fixtures.

3 1 1 2
1 3 0 2
0 0 0 0

188
200

Hint

In first test case, one optimal strategy is to yell “do it” in each of the first 25 time intervals. As a result, the 3 positively-responding employees provide 4 units of labor per time interval and thus finish their fixtures in 25 time units. The 1 negatively-responding employee will provide 1 unit of labor per time interval for the first 25 time intervals, 2 units of labor per time interval afterwards, and thus will finish in 25 + 38 = 63 time units. Finally, the neutral employee will always provide 2 units of labor per time interval and hence will finish in 50 time units. This gives a total of 3(25) + 63 + 50 = 188 time units.

In the second test case, an optimal strategy is to never yell “do it”. Thus all four employees finish in 50 time units so the total amount of time taken is 200 time units.

Source

Stanford Local 2005