题目描述

lizi_lzy有三个水桶，容量分别为 $a,b,c$。初始时，三个水桶里都没有水。

lizi_lzy的任务是通过反复倒水，使得最终存在一个桶的水量为 $V$ 。

为了达成任务，lizi_lzy可以进行以下操作：

• 选择一个桶，将该桶装满水。

• 选择一个桶，将该桶内的水倒光。

• 选择两个桶，将第一个水桶桶里的所有水倒向第二个水桶。（该操作可以执行，当且仅当两个水桶里的水的总量≤第二个水桶的容积。）

选择两个桶，将第一个水桶桶里的水倒向第二个水桶，直到第二个水桶装满。（该操作可以执行，当且仅当两个水桶里的水的总量≥≥第二个水桶的容积。）

lizi_lzy想知道他能否达成任务，如果能达成，最少通过多少步操作可以达成。

输入格式

第一行输入三个正整数 $a,b,c$，表示每个水桶的容量。

第二行输入一个正整数 $V$ ，表示lizi_lzy想要称出 $V$ 的水。

输出格式

在一行中输出一个整数，表示答案。

如果lizi_lzy不能完成任务，输出−1；否则输出lizi_lzy完成任务所需要的最少步数。

样例

2 3 5
4

4

3 4 5
2

2

4 6 8
5

-1

数据范围与提示

对于40%的数据，$1≤a,b,c, V ≤5$

对于100%的数据，$1≤a,b,c, V ≤200$