这是这个问题的简单版本。唯一的区别是,在此版本中您只需要输出最小的总运营成本。您必须解决这两个版本才能进行破解。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$m$$$ 的数组 $$$b$$$($$$b_i > b_{i+1}$$$ 对于所有 $$$1 \le i < m$$$)。最初,$$$k$$$ 的值为$$$1$$$。您的目标是通过重复执行以下两个操作之一来使数组 $$$a$$$ 为空:
- 输入 $$$1$$$ — 如果 $$$k$$$ 的值小于 $$$m$$$ 并且数组 $$$a$$$ 不为空,则可以将 $$$k$$$ 的值增加 $$$1$$$。这不会产生任何费用。
- 类型 $$$2$$$ - 删除数组 $$$a$$$ 的非空前缀,使其总和不超过 $$$b_k$$$。这会产生 $$$m - k$$$ 的成本。
您需要最小化使数组 $$$a$$$ 为空的操作总成本。如果通过任何操作序列都无法做到这一点,则输出 $$$-1$$$。否则,输出操作的最小总成本。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$\boldsymbol{1 \le n \cdot m \le 3 \cdot 10^5}$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$)。
对于所有 $$$1 \le i < m$$$,还保证 $$$b_i > b_{i+1}$$$。
保证所有测试用例的 $$$\boldsymbol{n \cdot m}$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果可以使 $$$a$$$ 为空,则输出操作的最小总成本。
如果没有可能的操作序列使 $$$a$$$ 为空,则输出单个整数 $$$-1$$$。
示例
输入 #1
5 4 2 9 3 4 3 11 7 1 2 20 19 18 10 2 2 5 2 1 10 3 2 9 9 6 17 9 10 11 2 2 2 2 2 2 2 2 2 2 20 18 16 14 12 10 8 6 4 2 1 1 6 10 32 16 8 4 2 1
输出 #1
1 -1 2 10 4
注意
在第一个测试用例中,产生总成本 $$$1$$$ 的最佳操作序列如下:
- 执行 $$$2$$$ 类型的操作。选择前缀 $$$[9]$$$。这会产生 $$$1$$$ 的费用。
- 执行 $$$1$$$ 类型的操作。 $$$k$$$ 的值现在是 $$$2$$$。这不需要任何费用。
- 执行 $$$2$$$ 类型的操作。选择前缀 $$$[3, 4]$$$。这会产生 $$$0$$$ 的费用。
- 执行 $$$2$$$ 类型的操作。选择前缀 $$$[3]$$$。这会产生 $$$0$$$ 的费用。
- 数组 $$$a$$$ 现在为空,所有操作的总成本为 $$$1$$$。
在第二个测试用例中,自 $$$a_1 > b_1$$$ 以来不可能删除数组的任何前缀,因此任何操作序列都不能将数组 $$$a$$$ 清空。