Given only two cups of sizes x and y, you would like to obtain a total amount of water in those two cups as close to the target sum s as possible.

You are allowed to perform up to k operations of the following form:

Fill one of the pails completely to the top

Empty one of the pails

Pour the contents of one pail into the other, stopping when the latter becomes full or the first one becomes empty (whichever happens first).

Initially, both of the pails are empty.

It might not be possible to obtain a total sum s in both pails, so you are asked to find the smallest difference |s - sβ|, where sβ is the collective water between two pails.

Input

The only line of the input contains 4 integers x, y (1 β€ x, y β€ 100), k (1 β€ k β€ 100), and s (1 β€ s β€ 200).

Output

The program should print the minimum absolute difference possible to obtain by performing at most k operations.

Examples

Input

Output

14 50 2 32

18

Explanation

We are allowed to perform only 2 operations. So, these are the possible outcomes after 2 operations:

(0, 0) β 0 units

(14, 0) β 14 units

(0, 50) β 50 units

(0, 14) β 14 units

(14, 36) β 50 units

(14, 50) β 64 units

Therefore, the closest to 32 we can get is 14, making the difference 18.

Note that we couldβve obtained 36 by emptying the first pail from (14, 36), yet that would require 3 steps, while weβre only allowed to perform at most 2.