Secchi per il latte (Argento)#10585

Secchi per il latte (Argento)

1 secondo

128 megabyte

Media

Il Fattore John ha ricevuto un ordine di esattamente $m$ unità di latte, che deve evadere immediatamente. Sfortunatamente, la sua moderna mungitrice si è appena rotta, e ora ha a disposizione solo due secchi per il latte con capacità intere $x$ e $y$ , che può usare per misurare la quantità di latte. Inizialmente entrambi i secchi sono vuoti.

Usando questi due secchi, può eseguire al massimo $k$ operazioni dei seguenti tipi:

Può riempire completamente uno qualsiasi dei secchi.
Può svuotare completamente uno qualsiasi dei secchi.
Può versare il contenuto di un secchio nell'altro, fermandosi quando il primo secchio si svuota oppure quando il secondo secchio si riempie, a seconda di quale evento si verifichi per primo.

Sebbene il Fattore John capisca che potrebbe non riuscire a ottenere esattamente $m$ unità di latte nei due secchi, aiutalo a determinare l'errore minimo possibile tra $m$ e la quantità totale di latte nei due secchi. In altre parole, occorre trovare il valore minimo di $∣ m - m^{'} ∣$ |m - m'|, tale che il Fattore John possa ottenere nei due secchi un totale di $m^{'}$ m' unità di latte.

Input

Una singola riga contiene quattro numeri interi $x, y, k$ x, y, k e $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

Stampa la differenza minima possibile tra $m$ e la quantità totale di latte che il Fattore John può ottenere.

Esempi

Con due operazioni, il Fattore John può ottenere nei suoi secchi le seguenti quantità di latte:

(0, 0) = 0 unità
(14, 0) = 14 unità
(0, 50) = 50 unità
(0, 14) = 14 unità
(14, 36) = 50 unità
(14, 50) = 64 unità

Più vicino a $32$ unità il Fattore John può arrivare ottenendo $14$ unità, ossia con una differenza di $18$ . Nota che, per svuotare il latte dal primo secchio e ottenere lo stato $(0, 36)$ , sarebbe stata necessaria un'altra operazione.

Esempio 1