Milk Pails

Interview

Time limit2sMemory limit512 MB

Summary

Fill, empty, and pour two pails of sizes X and Y within K moves to get a combined amount as close to M as possible.

Level: Medium4 of 10
Topics: BFS, Simulation
Solved: No attempts yet

Problem

Farmer John has an order for exactly $M$ units of milk ( $1 \le M \le 200$ ) and has to fill it right away. His milking machine just broke, so all he has left are two milk pails of integer sizes $X$ and $Y$ ( $1 \le X, Y \le 100$ ). Both pails start out empty. With these two pails he can perform up to $K$ operations ( $1 \le K \le 100$ ) of the following types.

Fill one pail completely to the top.
Empty one pail.
Pour the contents of one pail into the other, stopping when the pouring pail becomes empty or the receiving pail becomes full, whichever happens first.

The total in the two pails may never be exactly $M$ . Compute the minimum value of $|M - M'|$ over every total $M'$ that Farmer John can leave in the two pails.

Input

The first and only line contains $X$ , $Y$ , $K$ , and $M$ , separated by spaces.

Output

Print the smallest distance from $M$ to a total that Farmer John can produce.

Hint

For $X = 14$ , $Y = 50$ , $K = 2$ , and $M = 32$ , two operations leave the following amounts in the pails.

(0, 0) = 0
(14, 0) = 14
(0, 50) = 50
(0, 14) = 14
(14, 36) = 50
(14, 50) = 64

The totals closest to 32 are 14 and 50, both at a distance of 18. Reaching (0, 36) would take one more operation to empty the first pail.

Examples5

Example 1
Input
```
14 50 2 32
```
Expected output
```
18
```
Example 2
Input
```
7 11 2 18
```
Expected output
```
0
```
Example 3
Input
```
100 100 1 200
```
Expected output
```
100
```
Example 4
Input
```
13 17 6 200
```
Expected output
```
170
```
Example 5
Input
```
1 1 1 1
```
Expected output
```
0
```