Фермер Джон получил заказ доставить ровно \(M\) единиц молока (\(1 \leq M \leq 200\)).
К несчастью, его доильная машина сломалась и у него есть только два бидона с целочисленными размерами \(X\) и \(Y\) (\(1 \leq X, Y \leq 100\)), с помощью которых он может отмерять молоко. Оба бидона изначально пусты. Используя их, он может выполнять до \(K\) операций следующих типов (\(1 \leq K \leq 100\)):
- Он может заполнить любой бидон полностью
- Он может опорожнить полностью любой бидон.
- Он может переливать содержимое одного бидона в другой до тех пока, пока первый бидон не станет пустым, или второй бидон не станет полным (в зависимости от того, что произойдёт раньше).
ФД понял, что он может и не отмерять ровно \(M\) единиц молока, в двух бидонах. Помогите ему определить минимальную разность между \(M\) и суммарным молоком в двух баллонах. То есть, определите минимальное значение \(|M-M'|\) такое, что ФД может получить \(M'\) единиц молока в сумме содержимого двух бидонов.
ФОРМАТ ВВОДА (файл pails.in):
Первая и единственная строка ввода содержит \(X\), \(Y\), \(K\), \(M\).
ФОРМАТ ВЫВОДА (файл pails.out):
Выведите минимальное расстояние от \(M\), до количества молока, которое ФД сможет получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
14 50 2 32
|
18
|