珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

有容量分别为 X、Y 的两个水桶和充足水源。每次操作可以装满任意一桶、倒空任意一桶，或把一桶向另一桶倒水直到前者为空或后者装满。开始时两桶都为空。最多执行 K 次操作，求两桶水量之和与目标 M 的最小绝对差。

输入格式

输入一行四个整数 X、Y、K、M。

输出格式

输出不超过 K 次操作后，两桶总水量与 M 的最小绝对差。

51 75 1 3

3

77 87 8 41

21

70 19 13 93

4

数据范围与约定

• 1 ≤ X,Y,K,M ≤ 100