C. Bus

一辆公交车沿坐标轴 #cf_span[Ox] 从点 #cf_span[x = 0] 行驶到点 #cf_span[x = a]。从点 #cf_span[x = 0] 出发后，它到达点 #cf_span[x = a]，立即掉头返回点 #cf_span[x = 0]，再立即返回点 #cf_span[x = a]，如此反复。因此，公交车在 #cf_span[x = 0] 和 #cf_span[x = a] 之间往返。从 #cf_span[x = 0] 到 #cf_span[x = a] 或从 #cf_span[x = a] 到 #cf_span[x = 0] 的单程称为一次 _公交车行程_。总共，公交车必须完成 #cf_span[k] 次行程。 公交车的油箱容量为 #cf_span[b] 升汽油。每行驶一个单位距离，公交车恰好消耗一升汽油。公交车在第一次行程开始时油箱是满的。 在点 #cf_span[x = f] 处有一个加油站。该点位于 #cf_span[x = 0] 和 #cf_span[x = a] 之间，且公交车路线上的其他位置没有加油站。公交车在任意方向经过加油站时，可以停车并完全加满油箱。因此，停车加油后，油箱将重新充满 #cf_span[b] 升汽油。 问：为完成 #cf_span[k] 次行程，公交车在点 #cf_span[x = f] 处至少需要加多少次油？第一次行程从点 #cf_span[x = 0] 开始。 第一行包含四个整数 #cf_span[a], #cf_span[b], #cf_span[f], #cf_span[k]（#cf_span[0 < f < a ≤ 10^6]，#cf_span[1 ≤ b ≤ 10^9]，#cf_span[1 ≤ k ≤ 10^4]）——第一次行程的终点、油箱容量、加油站位置和所需的行程次数。 请输出公交车完成 #cf_span[k] 次行程所需的最少加油次数。如果无法完成 #cf_span[k] 次行程，请输出 _-1_。 ## Input 第一行包含四个整数 #cf_span[a], #cf_span[b], #cf_span[f], #cf_span[k]（#cf_span[0 < f < a ≤ 10^6]，#cf_span[1 ≤ b ≤ 10^9]，#cf_span[1 ≤ k ≤ 10^4]）——第一次行程的终点、油箱容量、加油站位置和所需的行程次数。 ## Output 请输出公交车完成 #cf_span[k] 次行程所需的最少加油次数。如果无法完成 #cf_span[k] 次行程，请输出 _-1_。 [samples] ## Note 在第一个例子中，公交车在每次行程中都需要加油。在第二个例子中，公交车在不加油的情况下可以行驶 #cf_span[10] 个单位距离。因此，公交车完成整个第一段行程，行驶第二段行程的 #cf_span[4] 个单位距离后到达加油站，然后加油，完成第二段行程，再行驶第三段行程的 #cf_span[2] 个单位距离，再次到达加油站。此时，它可以将油箱加满至 #cf_span[10] 升，完成第三段行程，并完成第四段行程的全部路程。在行程结束时，油箱为空。在第三个例子中，公交车无法完成全部 #cf_span[3] 次行程，因为如果在第二段行程中加油，油箱中将只剩下 #cf_span[5] 升汽油，而下一次加油前需要行驶 #cf_span[8] 个单位距离。

**Definitions** Let $ a, b, f, k \in \mathbb{Z}^+ $ be given, with $ 0 < f < a \leq 10^6 $, $ 1 \leq b \leq 10^9 $, $ 1 \leq k \leq 10^4 $. Let the bus make $ k $ journeys, each journey being a segment from $ x=0 $ to $ x=a $ or from $ x=a $ to $ x=0 $. The bus starts at $ x=0 $ with a full tank of $ b $ liters. A gas station is located at $ x = f $; refueling at this point resets the tank to $ b $ liters. Fuel consumption is 1 liter per unit distance. **Constraints** 1. The bus consumes fuel linearly: distance $ d $ requires $ d $ liters. 2. The bus can only refuel at $ x = f $, and only when passing through it (in either direction). 3. The tank capacity is $ b $; fuel level cannot exceed $ b $. 4. The bus must complete all $ k $ journeys without running out of fuel between refuels. **Objective** Compute the minimum number of refuels at $ x = f $ required to complete $ k $ journeys. If it is impossible, return $ -1 $. **Journey Types** - Odd-numbered journeys ($ 1,3,5,\dots $): $ 0 \to a $ - Even-numbered journeys ($ 2,4,6,\dots $): $ a \to 0 $ **Fuel Requirements per Segment** - From $ 0 $ to $ f $: $ f $ liters - From $ f $ to $ a $: $ a - f $ liters - From $ a $ to $ f $: $ a - f $ liters - From $ f $ to $ 0 $: $ f $ liters Thus: - Each $ 0 \to a $ journey requires: $ f + (a - f) = a $ liters total - Each $ a \to 0 $ journey requires: $ (a - f) + f = a $ liters total But fuel is consumed in segments, and refueling is only possible at $ f $. **Key Insight** The bus starts at $ 0 $ with full tank. We simulate journey-by-journey, tracking remaining fuel, and determine when refueling at $ f $ is necessary. Define: - $ \text{fuel} $: current fuel level (initially $ b $) - $ \text{refuels} = 0 $ For journey $ i = 1 $ to $ k $: - If $ i $ is odd: path = $ 0 \to a $ - Segment 1: $ 0 \to f $, consumes $ f $ - Segment 2: $ f \to a $, consumes $ a - f $ - If $ i $ is even: path = $ a \to 0 $ - Segment 1: $ a \to f $, consumes $ a - f $ - Segment 2: $ f \to 0 $, consumes $ f $ At each segment, if fuel is insufficient to reach the next refuel point (or destination), return $ -1 $. If the bus reaches $ f $ and cannot reach the next $ f $ (or end) without refueling, then refuel at $ f $. **Formal Objective** Minimize the number of refuels at $ x = f $ such that the bus completes $ k $ journeys without fuel depletion. Let $ r $ be the number of refuels. We seek the minimal $ r \in \mathbb{N}_0 $ such that the bus can complete $ k $ journeys under the constraints above. If no such $ r $ exists, output $ -1 $.