题目描述

有两个没有刻度的杯子，容量分别为 $X$ 和 $Y$。开始时，两个杯子都是空的。

每次可以进行下面一种操作：

1. 将一个杯子装满；
2. 将一个杯子清空；
3. 将一个杯子中的水倒入另一个杯子，直到前一个杯子变空或后一个杯子装满。

最多进行 $C$ 次操作后，设两个杯子中的水量之和为 $W$。请计算 $|W-N|$ 的最小值。可以少于 $C$ 次操作，也可以不进行任何操作。

输入格式

第一行包含 $4$ 个整数 $X,Y,C,N$，分别表示两个杯子的容量、最多操作次数和目标水量。

输出格式

输出一个整数，表示两个杯子的水量之和与目标水量的最小差值。

3 5 2 4

1

数据范围与提示

• $1 \le X,Y \le 1000$
• $0 \le C \le 100$
• $0 \le N \le 2000$