题目描述

$\red{Farmer John }$收到了一份需要立即装满 $\red{M }$单位牛奶 $\red{(1≤}$$\red{M≤}$$\red{200) }$的订单。

不幸的是，他的花哨的挤奶机刚刚坏了，他只有两个大小为整数 $\red{X }$和 $\red{Y （1≤}$$\red{X,Y≤}$$\red{100) }$的牛奶桶，他可以用它来量牛奶。

两个桶最初都是空的。使用这两个桶，他最多可以执行以下类型的操作中的 $\red{K }$个$\red{（1≤}$$\red{K≤}$$\red{100）}$：

$\red{- }$他可以将任一桶完全装满。 $\red{- }$他可以清空任何一个桶。

$\red{- }$他可以将一个桶的内容倒入另一个桶，当前者变空或后者变满时停止（以先发生者为准）。

尽管 $\red{FJ }$意识到他可能无法在两个桶中准确地得到总共 $\red{M }$个单位的牛奶，但请帮助他计算 $\red{M }$与两个桶中的牛奶总量之间的最小误差量。

即请计算$\red{|M-M′}$$\red{|}$的最小值。这样 $\red{FJ }$可以在两个桶之间共同构建 $\red{M' }$单位的牛奶。

输入格式

第一行，也是唯一一行输入，包含$\red{X}$、$\red{Y}$、$\red{K}$和$\red{M}$。

输出格式

输出从毫米到$\red{FJ}$能产生的牛奶量的最小距离。

样例

输入样例

14 50 2 32

输出样例

18

提示

在两个步骤中，$\red{FJ}$可以在他的桶中留下以下数量

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

单位我们可以得出的最接近$\red{32}$个单位是$\red{14，}$相差$\red{18}$。注意，倒出第一个桶需要额外的步骤才能得到（$\red{0，}$$\red{36）}$。