本题为的Hard版本，注意两题输出内容不同。在本题中，您需回答所有样例的最少运输次数。

Background

相信大家一定熟悉经典的农夫过河问题：农夫需要将狼、羊、白菜三样物品运送到河对岸，小船每次仅能承载农夫本人+一件物品。

但由于生物本能，若农夫不在场，则狼会吃羊，羊会吃菜。你的目标是规划过河顺序，让所有物品安全抵达对岸。

本题将对本经典问题进行拓展，并修改运输规则与安全条件。

Description

农夫养了 $x$ 只羊，一天 $y$ 只狼来到了河边。为了安全起见，农夫需要将所有羊安全运输回河对岸的羊圈中。

农夫有一条小船，其一次性最多可运输 $p$ 个物品(含农夫本人)，农夫本人可在两岸间自由往返。

但是，当任意一侧河岸上的动物不受农夫监管时(即农夫既不在此岸，也不在船上运输时)，若该岸同时存在狼和羊，且狼的数量 > 羊的数量 $+q$，则狼会吃掉羊。

农夫所在的河岸、船上运输中的动物，均受监管，绝对安全。

你需要求解：

• 将所有羊安全运送到对岸的最少运输次数；
• 若无论如何都无法安全运输，输出 -1 表示无解。

Format

Input

输入仅包含一行，包括 $4$ 个整数$x,y,p,q(1 \le x,y,p,q \le 100)$，分别代表羊的数量、狼的数量、船的承载数量、安全阈值。

输出格式

输出一行一个整数，表示将所有 $x$ 只羊安全运到对岸所需的最少运输次数；若无解，则输出 -1。

样例

4 4 3 1

3

3 5 2 0

5

2 5 1 1

-1

说明/提示

第一个样例的可能解法

• 题源：2023 ICPC 沈阳 E题