农夫约翰收到了一个订单,要求他提供恰好 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' 单位的牛奶。
输入的第一行,也是唯一一行,包含 X、Y、K 和 M。
输出农夫约翰可以产生的牛奶量与 M 的最小距离。
14 50 2 32
18
In two steps FJ can be left with the following quanities in his pails
(0, 0) = 0 units
(14, 0) = 14 units
(0, 50) = 50 units
(0, 14) = 14 units
(14, 36) = 50 units
(14, 50) = 64 units
The closest we can come to 32 units is 14 for a difference of 18. Note that it
would require an extra step to pour out the first pail to end up with (0, 36).