Farmer John 接到了一份需要立即完成的订单，要求他提供恰好 M 单位的牛奶（1 \leq M \leq 200）。不幸的是，他先进的挤奶机刚刚坏了，现在他只有两个容量为整数 X 和 Y（1 \leq X, Y \leq 100）的牛奶桶可以用来量取牛奶。两个桶最初都是空的。使用这两个桶，他可以执行最多 K 次以下类型的操作（1 \leq K \leq 100）：

• 他可以将任意一个桶完全装满。

• 他可以将任意一个桶完全倒空。

• 他可以将一个桶中的牛奶倒入另一个桶，直到前者被倒空或后者被装满（以先发生的情况为准）。

尽管 FJ 意识到他可能无法最终在两个桶中得到恰好 M 单位的牛奶，但请帮助他计算 M 与两个桶中牛奶总量之间的最小误差。也就是说，请计算 |M-M'| 的最小值，其中 M' 是 FJ 可以在两个桶中共同构造的牛奶量。

输入的第一行也是唯一一行包含 X、Y、K 和 M。

输出 M 与 FJ 可以生产的牛奶量之间的最小误差。

在两步操作中，FJ 可以在他的桶中留下以下数量的牛奶：

(0, 0) = 0 单位  
(14, 0) = 14 单位  
(0, 50) = 50 单位  
(0, 14) = 14 单位  
(14, 36) = 50 单位  
(14, 50) = 64 单位  

最接近 32 单位的是 14 单位，误差为 18。注意，要倒空第一个桶以得到 (0, 36) 需要额外的步骤。

USACO