Milk Pails Measurement

Farmer John has received an order for exactly $M$ units of milk ($1 \le M \le 200$) that he needs to fill immediately. Unfortunately, his fancy milking machine is broken, and he only has two milk pails of integer sizes $X$ and $Y$ ($1 \le X, Y \le 100$). Both pails are initially empty. Using these two pails, he can perform up to $K$ ($1 \le K \le 100$) operations. The available operations are:

• Fill either pail completely.
• Empty either pail.
• Pour milk from one pail to the other until the source pail is empty or the destination pail is full.

Even if it is not possible to obtain exactly $M$ units of milk, your task is to compute the minimum absolute difference $|M-M'|$, where $M'$ is the total amount of milk in the two pails after at most $K$ operations.

inputFormat

The input consists of a single line containing four space-separated integers: X, Y, K, and M.

outputFormat

Output a single integer representing the minimum absolute difference between M and the total amount of milk achievable using at most K operations.

sample

14 50 2 32

18