AT_awtf2024_c Fuel

你面前有 $ T $ 个测试用例需要解决。 你当前在数轴的起始位置 $ 0 $，目标是到达位置 $ L $。 你将使用一辆车前进，这辆车需要依靠两种不同类型的燃料：类型 $ 1 $ 和类型 $ 2 $。每种燃料的油箱容量都是 $ C $ 升，目前两个油箱都是满的。在移动时，你可以选择任何一种燃料，消耗 $ x $ 升（$ x $ 是不超过当前剩余燃料的正整数），这样车就可以在数轴上向任何方向移动 $ x $ 的距离。 在数轴上分布着 $ N $ 个加油站。第 $ i $ 个加油站位于坐标 $ X_i $。当车停在某个加油站时，你可以以每升燃料 $ 1 $ 的成本购买类型 $ K_i $ 的燃料，不过要注意，不可以超过油箱的容量。 请判断是否能到达坐标 $ L $，如果可以，请计算达到目标所需的最小燃料成本。

输入通过标准输入，以以下格式给出： > $ T $ > $ case_1 $ > $ case_2 $ > $ \vdots $ > $ case_T $ 每个测试用例的格式如下： > $ N $ $ L $ $ C $ > $ X_1 $ $ X_2 $ $ \cdots $ $ X_N $ > $ K_1 $ $ K_2 $ $ \cdots $ $ K_N $

输出共 $ T $ 行。对于第 $ i $ 个测试用例： - 如果无法到达 $ L $，输出 $ -1 $； - 如果能够到达，输出所需的最小采购成本。 ## 数据范围 - $ 1\ \leq\ T\ \leq\ 250000 $ - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ L\ \leq\ 10^9 $ - $ 1\ \leq\ C\ \leq\ 10^9 $ - $ 0\

### 制約 - $ 1\ \leq\ T\ \leq\ 250000 $ - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ L\ \leq\ 10^9 $ - $ 1\ \leq\ C\ \leq\ 10^9 $ - $ 0\