题目描述

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 可以生产的牛奶量之间的最小误差。

14 50 2 32

18

说明

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

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

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