두더지 찾기

시간 제한2초메모리 제한1024 MB

요약

각 구멍 i에 A_i의 배수 시각마다 두더지가 나타날 때, 상태가 배열 B와 일치하는 가장 작은 시각 T를 1부터 L 사이에서 구합니다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

근수 앞에 $N$ 개의 두더지 구멍이 한 줄로 놓여 있다. 정수 시각 $T$ 가 $A_i$ 의 배수이면 $i$ 번째 구멍에 두더지가 나타나고, 그렇지 않으면 나타나지 않는다. 근수는 구멍들의 상태가 배열 $B$ 와 일치하기를 바란다. $B_i = 1$ 이면 $i$ 번째 구멍에 두더지가 있어야 하고, $B_i = 0$ 이면 없어야 한다. 시각은 정수만 고려한다.

근수는 시각 $1$ 부터 $L$ 까지 두더지를 관찰한다. 이 범위에서 구멍의 상태가 $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을 출력한다.

예제2

예제 1
입력
```
3 30
2 3 5
1 0 1
```
예상 출력
```
10
```
예제 2
입력
```
3 5
2 3 5
1 1 0
```
예상 출력
```
-1
```