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

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

• Наповнити будь-який бідон повністю.

• Спорожнити будь-який бідон повністю.

• Перелити вміст одного бідона в інший, поки перший бідон не стане порожнім або другий не наповниться (залежно від того, що станеться раніше).

Фермер Джон зрозумів, що він може не відміряти рівно m одиниць молока у двох бідонах. Допоможіть йому визначити мінімальну різницю між m і сумарним молоком у двох бідонах. Тобто, знайдіть мінімальне значення |m − m′|, де m' — це кількість молока, яку Фермер Джон може отримати у сумі вмісту двох бідонів.

Вхідні дані

Один рядок містить x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) і m (1 ≤ m ≤ 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).