题目描述

小 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$。

0 3
3 1
1
1
3 2
2 3
1 1
4 2
2 4
2 3

2
3
-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$		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$ 均相同。