Відра для молока (Срібло)#10585

Відра для молока (Срібло)

1 секунда

128 мегабайтів

Середня

Фермер Джон отримав замовлення рівно на $m$ одиниць молока, яке йому необхідно виконати негайно. На жаль, його сучасна доїльна машина щойно зламалася, і тепер у нього є лише два відра для молока з цілочисельними об'ємами $x$ і $y$ , які він може використовувати для вимірювання кількості молока. Спочатку обидва відра порожні.

Використовуючи ці два відра, він може виконати не більше $k$ операцій наступних типів:

Він може повністю наповнити будь-яке з відер.
Він може повністю спорожнити будь-яке з відер.
Він може переливати вміст одного відра в інше, зупиняючись, коли перше відро спорожніє або друге відро заповниться, залежно від того, що станеться раніше.

Хоча Фермер Джон розуміє, що, можливо, йому не вдасться отримати рівно $m$ одиниць молока у двох відрах, допоможіть йому визначити мінімальну можливу похибку між $m$ та загальною кількістю молока у двох відрах. Іншими словами, необхідно знайти мінімальне значення $∣ m - m^{'} ∣$ |m - m'|, таке що Фермер Джон зможе отримати у двох відрах загалом $m^{'}$ m' одиниць молока.

Вхідні дані

В одному рядку містяться чотири цілих числа $x, y, k$ x, y, k та $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).

Вихідні дані

Виведіть мінімально можливу різницю між $m$ та загальною кількістю молока, яке Фермер Джон може отримати.

Приклади

За дві операції Фермер Джон може отримати у своїх відрах наступні кількості молока:

(0, 0) = 0 одиниць
(14, 0) = 14 одиниць
(0, 50) = 50 одиниць
(0, 14) = 14 одиниць
(14, 36) = 50 одиниць
(14, 50) = 64 одиниці

Найближче Фермер Джон може наблизитися до $32$ одиниць, отримавши $14$ одиниць, тобто різниця становить $18$ . Зверніть увагу, що для того, щоб вилити молоко з першого відра та отримати стан $(0, 36)$ , знадобилася б ще одна операція.

Приклад 1