P14508 猜数游戏 guess

小 P 在玩一种新型的猜数游戏。他有一个一行无数格的棋盘，在棋盘的编号为 $1$ 的格子处有一枚棋子，这枚棋子有 $m$ 种移动方式，第 $i$ 种移动方式可以使这枚棋子向左或向右移动 $a_i$ 格，使用这种方式移动的花费为 $b_i$。在棋盘上有一个隐藏的目标位置，当小 P 知道了目标位置时，游戏胜利。 当棋子从位置 $x$ 移动到位置 $x+y$ 时，它会询问 $[x,x+y)$ 是否包含目标位置。同理，当棋子从位置 $x$ 移动到位置 $x-y$ 时，它会询问 $[x-y,x)$ 是否包含目标位置（$y \ge 0$）。由于棋盘无限大，所以可以移动到负数位置。 现在小 P 已经知道目标位置在 $[1,n]$ 范围内，现在请你帮他求出，在采取最优策略时（可以根据询问的结果来决定策略），最坏情况需要花费多少才能获得胜利，若无法取得胜利，输出 $-1$。

**本题有多组测试数据**。 输入的第一行包含两个整数 $c,T$，表示测试点编号和测试数据的组数。 接下来包含 $T$ 组数据，每组数据的格式如下: * 第一行包含两个整数 $n,m$，表示目标位置的范围和移动方式的数量。 * 第二行包含 $m$ 个整数 $a_1, a_2, \dots,a_m$ 表示第 $i$ 种移动方式移动的格数。 * 第三行包含 $m$ 个整数 $b_1, b_2, \dots,b_m$ 表示第 $i$ 种移动方式所需的代价。

对于每组测试数据输出一个整数，表示取得胜利的最小花费。若无法取得胜利，输出 $-1$。

**【样例 1 解释】** 对于第一组数据，最坏情况目标位置为 $3$，棋子向右移动 $2$ 格，可以判断出不是 $1$ 或 $2$，即可得出答案。 对于第二组数据，一种可能的跳法为 $1\to3\to0\to2$，可以证明没有更优的方法。 **【样例 2】** 见附件的 guess/guess2.in 与 guess/guess2.ans。 该样例满足测试点 $2\sim 3$ 的约束条件。 **【样例 3】** 见附件的 guess/guess3.in 与 guess/guess3.ans。 该样例满足测试点 $4$ 的约束条件。 **【样例 4】** 见附件的 guess/guess4.in 与 guess/guess4.ans。 该样例满足测试点 $7\sim 11$ 的约束条件。 **【样例 5】** 见附件的 guess/guess5.in 与 guess/guess5.ans。 该样例满足测试点 $15\sim 25$ 的约束条件。 **【数据范围】** 对于所有的数据，满足: * $1\le T\le 10$。 * $1\le n\le 10^4$，$1\le m\le 1000$，$1\le a_i\le \min(n,1000)$，$1\le b_i\le 10^9$。 ::cute-table{tuack} | 测试点编号 | $n\leq$ | $m \leq$ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | A | | $2\sim 3$ | ^ | ^ | 无 | | $4$ | $100$ | $20$ | B | | $5\sim 6$ | ^ | ^ | 无 | | $7\sim 11$ | $3000$ | $100$ | ^ | | $12\sim 14$ | $10^4$ | $1000$ | B | | $15\sim 25$ | ^ | ^ | 无 | - 特殊性质 A：保证所有 $a_i$ 均相同。 - 特殊性质 B：保证所有 $b_i$ 均相同。