← 返回题目列表

Codeforces · 864/C

C. 巴士

中文机器翻译题面 查看原题

一辆公交车沿着坐标线Ox从点x=0移动到点x=a。从x = 0点出发,到达x = a点后,立即返回,然后移动到x = 0点。返回到x = 0点后,立即返回x = a点,以此类推。因此,总线从 x = 0 移动到 x = a 并返回。从点 x = 0 到 x = a 或从点 x = a 到 x = 0 称为巴士旅程。总共,公共汽车必须进行 k 次行程。

公交车的油箱可容纳b升汽油。为了通过一个单位的距离,公共汽车需要消耗一升汽油。巴士在油箱已满的情况下开始了第一次旅程。

在点 x = f 处有一个加油站。该点位于点 x = 0 和 x = a 之间。巴士路线上没有其他加油站。当公交车从任一方向经过加油站时,都可以停下来并完全加满油。因此,停车加油后,油箱中将含有 b 升汽油。

公交车在 x = f 点至少需要加油多少次才能完成 k 趟旅程?第一个旅程从 x = 0 点开始。

输入

第一行包含四个整数a、b、f、k(0 < f < a ≤ 106, 1 ≤ b ≤ 109, 1 ≤ k ≤ 104)——第一趟公交车旅程的终点、公交车油箱的容量、加油站所在的地点以及所需的行程次数。

输出

打印公交车完成 k 趟旅程所需加油的最少次数。如果公共汽车不可能完成 k 趟行程,则打印 -1。

示例

输入 #1

6 9 2 4

输出 #1

4

输入 #2

6 10 2 4

输出 #2

2

输入 #3

6 5 4 3

输出 #3

-1

注意

在第一个示例中,公交车在每次行程中都需要加油。

在第二个示例中,公交车无需加油即可行驶 10 个单位的距离。因此,巴士完成第一趟旅程,经过第二趟旅程的 4 个单位的距离,到达有加油站的地点。然后它可以给油箱加油,完成第二次旅程并从第三次旅程中经过2个单位的距离。在这种情况下,它会再次到达有加油站的点。此外,他还可以将油箱加满10升,以完成第三趟旅程,并一路骑行第四趟旅程。旅程结束时,水箱将空。

在第三个示例中,公交车无法完成全部 3 趟旅程,因为如果在第二趟旅程中加油,油箱中将仅含有 5 升汽油,但公交车需要经过 8 个单位的距离才能进行下一次加油。