Milk Pails (Silver)#10585

Milk Pails (Silver)

1 second

128 megabytes

Medium

Farmer John has received an order for exactly $m$ units of milk that he needs to fill immediately. Unfortunately, his fancy milking machine has just broken, and all he has are two milk pails with integer capacities $x$ and $y$ that he can use to measure milk. Both pails are initially empty.

Using these two pails, he can perform at most $k$ operations of the following types:

He can fill either pail completely.
He can empty either pail.
He can pour the contents of one pail into the other, stopping when the first pail becomes empty or the second pail becomes full, whichever happens first.

Although FJ realizes that he may not be able to end up with exactly $m$ units of milk in the two pails, please help him determine the minimum possible error between $m$ and the total amount of milk in the two pails. In other words, compute the minimum value of $∣ m - m^{'} ∣$ |m - m'| such that FJ can obtain a total of $m^{'}$ m' units of milk in the two pails.

Input

One line contains four integers $x, y, k$ x, y, k, and $m (1 \leq x, y \leq 100, 1 \leq k \leq 100, 1 \leq m \leq 200)$ m~(1 \le x, y \le 100, 1 \le k \le 100, 1 \le m \le 200).

Output

Print the minimum possible difference between $m$ and the total amount of milk FJ can produce.

Examples

In two steps, FJ can obtain the following amounts of milk in his pails:

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

The closest FJ can get to $32$ units is $14$ units, for a difference of $18$ . Note that it would require an additional step to empty the first pail and obtain $(0, 36)$ .

Example 1