Water Pails

Dado que solo dispones de dos cubos de tamaños x y y, tu objetivo es obtener la cantidad total de agua en esos dos cubos lo más cercana posible al valor objetivo s.

Tienes permitido realizar como máximo k operaciones de los siguientes tipos:

• Llenar uno de los cubos completamente.

• Vaciar uno de los cubos.

• Verter el contenido de un cubo en el otro, deteniéndote cuando el segundo se llene o cuando el primero se vacíe (lo que suceda primero).

Al inicio, ambos cubos están vacíos.

Es posible que no logres exactamente la suma s en ambos cubos, así que necesitas determinar la diferencia más pequeña |s - s’|, donde s’ representa la cantidad total de agua que hay en los dos cubos combinados.

Input

La única línea de la entrada contiene 4 enteros x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) y s (1 ≤ s ≤ 200).

Output

El programa debe mostrar la menor diferencia absoluta posible que puedas obtener ejecutando, como máximo, k operaciones.

Examples

Explanation

Solo se permiten 2 operaciones. A continuación se muestran todos los resultados posibles después de hacer 2 operaciones:

1. (0, 0) → 0 unidades

2. (14, 0) → 14 unidades

3. (0, 50) → 50 unidades

4. (0, 14) → 14 unidades

5. (14, 36) → 50 unidades

6. (14, 50) → 64 unidades

La cantidad más cercana a 32 que podemos obtener es 14, de modo que la diferencia es 18.

Observa que podríamos haber llegado a 36 vaciando el primer cubo a partir de (14, 36), pero eso hubiera requerido 3 pasos, y solo tenemos permitido realizar 2 como máximo.