题目描述

小明拥有两个杯子 $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$ ，分别表示杯子 $A$ 的容量、杯子 $B$ 的容量、最大操作步数、目标水量 。其中 $1 \leq X, Y \leq 100$ ，$1 \leq N \leq 200$ ，$1 \leq C \leq 100$ 。

输出格式

输出一个整数，即两个杯子装的水总量与 $N$ 的差值的最小值。

示例

• 输入示例1

10 15 2 7

• 输出示例1

3

• 解释：初始时 $A$、$B$ 两杯子水量为 $0,0$ 。第一步可选择装满 $A$ 或 $B$ ，得到 $10,0$ 或 $0,15$ 。第二步有多种选择，如在 $10,0$ 基础上装满 $B$ 得 $10,15$ ，或在 $10,0$ 基础上将 $A$ 倒入 $B$ 得 $0,10$ 等。在所有可能状态中，两杯子水量之和与 $7$ 的最小差值为 $10 - 7 = 3$ 。
• 输入示例2

85 15 5 36

• 输出示例2

6

• 输入示例3

71 37 5 95

• 输出示例3

10