题目描述

你面前有 $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 自动生成

输入输出样例 #1

输入 #1

5
1 10 4
7
1
1 10 6
7
1
2 12 3
5 7
1 1
2 12 3
5 7
1 2
20 749013197 23809523
46981984 70791437 118235723 132421762 180040807 203849360 251468335 275277857 322889975 346699150 394318091 418113855 465732891 489532137 537144103 558852533 606466719 630275002 677584754 701394209
1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2

输出 #1

2
0
-1
6
585545066743659