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\ <\ X_1\ <\ X_2\ <\ \cdots\ <\ X_N\ <\ L $
• $ K_i=1 $ 或 $ 2 $
• 所有测试用例中，$ N^2 $ 的总和不超过 $ 5000^2 $
• 所有输入值均为整数

示例解释 1

第一个测试用例可以通过以下步骤以成本 $ 2 $ 到达坐标 $ L $：

• 消耗 $ 3 $ 升类型 $ 1 $ 的燃料，从坐标 $ 0 $ 移动到 $ 3 $，此时类型 $ 1 $ 燃料剩余 $ 1 $ 升。
• 消耗 $ 4 $ 升类型 $ 2 $ 的燃料，从坐标 $ 3 $ 移动到 $ 7 $，类型 $ 2 $ 燃料耗尽。
• 在加油站购买 $ 2 $ 升类型 $ 1 $ 的燃料，使类型 $ 1 $ 燃料达 $ 3 $ 升。
• 再消耗 $ 3 $ 升类型 $ 1 $ 的燃料，从坐标 $ 7 $ 移动到 $ 10 $，类型 $ 1 $ 燃料耗尽。

无法在 $ 2 $ 以内的成本到达 $ L $，因此答案是 $ 2 $。

本翻译由 AI 自动生成