32633번 - 두더지 찾기

문제

근수 앞에 $N$개의 두더지 구멍이 순서대로 놓여 있다. 현재 시각 $T$가 $A_i$의 배수라면 $i$번째 구멍에 두더지가 나타나고 그렇지 않다면 $i$번째 구멍에는 두더지가 나타나지 않는다. 또한 근수는 두더지들의 상태가 배열 $B$를 만족하기를 바란다. $B_i = 1$이면 $i$번째 구멍에 두더지가 있어야 하고 $B_i = 0$이면 $i$번째 구멍에는 두더지가 없어야 한다. (이 문제에서의 시각은 정수 시각만 고려한다.)

근수는 시각 1ドル$부터 $L$까지 두더지들을 관찰하였을 때 배열 $B$를 만족하는 시각이 있는지 알고 싶다. 근수가 두더지들을 관찰하는 동안 배열 $B$를 만족하는 시각이 있는지 구하고, 있다면 이를 만족하는 가장 작은 정수 시각 $T$를 구해보자.

입력

첫 번째 줄에 정수 $N$과 $L$이 주어진다. $(1 \leq N \leq 10^5, 1 \leq L \leq 10^{12})$

두 번째 줄에 정수 $A_1, A_2, \dots, A_N$이 주어진다. $(1 \leq A_i \leq 10^5)$

세 번째 줄에 정수 $B_1, B_2, \dots, B_N$이 주어진다. $(B_i \in \{0, 1\})$

출력

배열 $B$를 만족하는 가장 작은 정수 시각 $T$를 출력한다. 만약 그러한 $T$가 없다면 -1을 출력한다.

제한

힌트