시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)44614112734.417%

문제

근수 앞에 $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을 출력한다.

예제 입력 1

3 30
2 3 5
1 0 1

예제 출력 1

10

예제 입력 2

3 5
2 3 5
1 1 0

예제 출력 2

-1

출처

University > 서강대학교 > Sogang Programming Contest > 2024 Sogang Programming Contest > Champion D번