← 返回题目列表

Codeforces · 2145/F

F. 漫长的旅程

中文机器翻译题面 查看原题

有一个条带分为多个单元,从左到右编号为 $$$0$$$ 到 $$$m$$$。您正在控制最初位于单元$$$0$$$中的芯片。

每个牢房内都有一个陷阱;它们根据以下规则激活:

  • 在移动 $$$1、(1+n)、(1+2n)、\dots$$$ 结束时,在单元格 $$$x$$$ 中激活陷阱,其中 $$$x \bmod a_1 = b_1$$$;
  • 在移动 $$$2、(2+n)、(2+2n)、\dots$$$ 结束时,陷阱在单元格 $$$x$$$ 中被激活,其中 $$$x \bmod a_2 = b_2$$$;
  • $$$\cdots$$$
  • 在移动 $$$n、(n+n)、(n+2n)、\dots$$$ 结束时,陷阱在单元格 $$$x$$$ 中激活,其中 $$$x \bmod a_n= b_n$$$。

在一个回合中,你可以从当前单元格移动到下一个单元格,也可以留在原地。然后本回合的所有陷阱都会被激活。如果筹码在回合开始时位于已激活陷阱的单元格中,则游戏结束。

你的任务是计算到达单元格$$$m$$$的最小转弯数,或者报告这是不可能的。 如果筹码到达单元格 $$$m$$$ 并且在同一回合结束时,单元格 $$$m$$$ 中的陷阱激活,则不被视为到达单元格 $$$m$$$ 的有效方式.

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10$$$; $$$1 \le m \le 10^{12}$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \lt a_i$$$)。

输出

对于每个测试用例,打印一个整数 - 到达单元格 $$$m$$$ 的最小圈数。如果不可能,则打印 -1.

示例

输入
复制

5
2 5
2 2
0 1
2 5
2 2
1 0
1 7
3
2
4 212398151713
3 2 5 2
0 1 3 0
2 4
3 4
0 0

输出
复制

5
6
-1
424796303424
5