El Granjero Juan ha recibido una orden de exactamente ~M~ unidades de leche ~(1 \leq M \leq 200)~ que él necesita despachar inmediatamente. Desafortunadamente, su máquina elegante de ordeñar se ha dañado y todo lo que él tiene son dos cántaros de leche de tamaños enteros ~X~ y ~Y~ ~(1 \leq X,Y \leq 100)~ con los cuales él puede medir leche. Ambos cántaros están inicialmente vacíos. Usando esos dos cántaros, él puede ejecturar hasta ~K~ veces una de los siguientes tipos de operaciones ~(1 \leq K \leq 100)~:

• El puede llenar completamente un cántaro hasta el tope.

• El puede vaciar cualquier cántaro.

• El puede vaciar el contenido de un cántaro en el otro, parando cuando el primero quede vacío cuando el segundo quede lleno (lo que pase primero).

Aunque GJ se da cuenta que él podría no ser capaz de quedarse con exactamente ~M~ unidades totales de leche en los dos cántaros, por favor ayúdelo a calcular la cantidad mínima de error entre ~M~ y la cantidad total de leche en los dos cántaros. Esto es, por favor, calcule el valor mínimo de ~|M-M'|~ donde GJ puede obtener ~M'~ unidades de leche colectivamente entre los dos cántaros.

Entrada

La primera y única línea de la entrada contiene ~X~, ~Y~, ~K~ y ~M~.

Salida

Dé como salida la distancia mínima de ~M~ a una cantidad de leche que GJ puede producir.

Ejemplo de Entrada

14 50 2 32

Ejemplo de Salida

18

En dos pasos GJ puede quedarse con las siguientes cantidades en sus cántaros

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

Lo más cerca que podemos estar a 32 unidades es 14 unidades para una diferencia de 18. Note que se requeriría un paso extra para vaciar el primer cántaro y terminar con (0, 36).