CF1148B Born This Way

$Arkady$ 买了一张从 $A$ 市到 $C$ 市的机票。不幸的是，这两个城市之间没有直飞航班，但是从 $A$ 市到 $B$ 市和从 $B$ 市到 $C$ 市的航班有很多。 从 $A$ 市到 $B$ 市有 $N$ 个航班，它们分别在 $a_1,a_2,a_3,...$ $,a_n$ 时起飞，在 $ta$ 个单位时间的飞行后到达 $B$ 市。 从 $B$ 市到 $C$市 有 $M$ 个航班，它们在 $b_1,b_2,b_3,...$ $,b_m$ 起飞。在 $tb$ 个单位时间的飞行后到达 $C$ 市。 转机的时间忽略不计，因此只有当 $b_j \ge a_i+ta$ 时，$Arkady$ 才能搭乘从 $A$ 市到 $B$ 市的第 $i$ 次航班和 $B$ 市到 $C$ 市的第 $j$ 次航班抵达目的地。 你最多可以不择手段地取消 $k$ 次航班。如果你取消了航班，$Arkady$ 当然就不能搭乘它了。 $Arkady$ 想尽早到 $C$ 市，而你想让他尽可能地晚到 $C$ 市。计算你取消了 $k$ 次航班之后 $Arkady$ 最早到达 $C$ 市的时间点。如果你可以通过取消 $k$ 次或更少的航班，使 $Arkady$ 不能达到 $C$ 市，请输出 $−1$ 。

无

无

Consider the first example. The flights from A to B depart at time moments $ 1 $ , $ 3 $ , $ 5 $ , and $ 7 $ and arrive at B at time moments $ 2 $ , $ 4 $ , $ 6 $ , $ 8 $ , respectively. The flights from B to C depart at time moments $ 1 $ , $ 2 $ , $ 3 $ , $ 9 $ , and $ 10 $ and arrive at C at time moments $ 2 $ , $ 3 $ , $ 4 $ , $ 10 $ , $ 11 $ , respectively. You can cancel at most two flights. The optimal solution is to cancel the first flight from A to B and the fourth flight from B to C. This way Arkady has to take the second flight from A to B, arrive at B at time moment $ 4 $ , and take the last flight from B to C arriving at C at time moment $ 11 $ . In the second example you can simply cancel all flights from A to B and you're done. In the third example you can cancel only one flight, and the optimal solution is to cancel the first flight from A to B. Note that there is still just enough time to catch the last flight from B to C.