题目描述

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

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

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

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

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

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

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

输入格式

第一行，也是唯一一行输入，包含${X}$、${Y}$、${K}$和${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）}$。