F. Долгое путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть полоса, разделенная на ячейки, пронумерованные от $$$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