Secchi d’Acqua

Se hai soltanto due recipienti di capacità x e y, il tuo obiettivo è ottenere una quantità totale di acqua in questi due recipienti che sia la più vicina possibile a un determinato valore s.

Hai la possibilità di compiere fino a k operazioni tra le seguenti:

• Riempire completamente uno dei due recipienti

• Svuotare uno dei due recipienti

• Versare il contenuto di un recipiente nell’altro, fermandoti non appena il secondo è pieno oppure il primo è vuoto (a seconda di cosa accade prima).

All’inizio, entrambi i recipienti sono vuoti.

Potrebbe non essere sempre possibile ottenere esattamente la somma s in entrambi i recipienti. Per questo motivo, ti viene richiesto di trovare la differenza minima |s - s’|, dove s’ è il quantitativo complessivo di acqua nei due recipienti.

Input

L’unica riga dell’input contiene 4 interi x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) e s (1 ≤ s ≤ 200).

Output

Il programma deve stampare la minima differenza assoluta ottenibile eseguendo al massimo k operazioni.

Esempi

Spiegazione

È possibile effettuare solo 2 operazioni. Ecco le situazioni raggiungibili dopo 2 operazioni:

1. (0, 0) → 0 unità

2. (14, 0) → 14 unità

3. (0, 50) → 50 unità

4. (0, 14) → 14 unità

5. (14, 36) → 50 unità

6. (14, 50) → 64 unità

La quantità più vicina a 32 è 14, con una differenza di 18.

Da notare che saremmo potuti arrivare a 36 svuotando il primo recipiente partendo da (14, 36), ma ciò avrebbe richiesto 3 operazioni, mentre il limite massimo è 2.