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

Фермер Джон получил заказ доставить ровно 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 units
(14, 0) = 14 units
(0, 50) = 50 units
(0, 14) = 14 units
(14, 36) = 50 units
(14, 50) = 64 units

Ближайшее значение к 32 это 14 и разность 18. Заметим, что требуется лишний шаг, чтобы получить (0, 36).