小明有 A B 两个杯子，容量分别为 X 升、Y 升。

他想用这两个杯子，通过如下的操作，装出总和恰好为 N 升的水。

每一步，他都可以执行下面动作中的一个动作：

1. 装满杯子 A。

2. 装满杯子 B。

3. 将 A 中的水，倒入杯子 B，直到 A 倒空或者 B 倒满。

4. 将 B 中的水，倒入杯子 A，直到 B 倒空或者 A 倒满。

5. 将杯子 A 中的水，倒入水池，清空杯子 A。（该操作不影响杯子 B 中的水）

6. 将杯子 B 中的水，倒入水池，清空杯子 B。（该操作不影响杯子 A 中的水）

经过几次实验后，小明意识到，他可能无论如何都无法得到总和恰好 N 升水。于是他给自己设置了一个要求：只能做不超过 C 步。

请你编程帮助小明计算出，如果只能做不超过 C 步，那么小明通过两个杯子能装出的水的总量（即：两个杯子中水的体积和），和 N 的差值的最小值是多少？

输入 4 个整数：X Y C N，含义如题所述。

输出一个整数，代表最小差值。

样例 1 解释

初始状态下 A,B 两个杯子的容量分别为 0,0。

第一步：可以选择装满 A 或者装满 B，可以得到两个杯子的容量分别为：10,0、0,15。

第二步：可以有如下选择。

在 10,0 的基础上，装满 B，得到 10,15，同理也可以在 0,15 的基础上装满 A。

在 10,0 的基础上，将 A 倒入 B，得到 0,10。

在 0,15 的基础上，将 B 倒入 A，得到 10,5。

当然，也可以选择将一个杯子清空，得到 0,0。

在上述所有的状态中，两个杯子的容量之和与 7 的最小差值为 10-7=3。

数据范围

对于 20\% 的数据，满足 C \le 2。

对于 100\% 的数据，满足 1 \le X,Y \le 100，1 \le N \le 200，1 \le C \le 100。

月赛搜索2024