Product

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

요약

100 이하의 서로 다른 소수 k개와 10^18 이하의 N이 주어질 때, 소인수가 모두 그 집합에 속하면서 N을 넘지 않는 가장 큰 수를 찾는다.

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

문제

Warning: Pay attention to the unusual memory limit.

You are given $k$ prime numbers $p\_1, p\_2 \dots, p\_k$ and an integer $N$ . Your task is to find the largest integer not exceeding $N$ whose prime factorization contains only these prime numbers.

For example, if the prime numbers are $2, 3, 7$ , the set of numbers whose factorization contains only these primes is $\\{1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 27, 28, 32, 36, 42, 48, 49, 54, 56, 63, 64, 72, 81, 84, 96, 98, \ldots \\}$ .

입력

The first line of the input contains two integers $k, N$ ( $k \ge 1$ , $1 \le N \le 10^{18}$ ) described above. The second line contains $k$ distinct prime numbers $p\_1, \dots, p\_k$ ( $2 \le p\_i \le 100$ ).

출력

You should output a single positive integer -- the largest number not exceeding $N$ whose prime factorization contains only prime numbers $p\_1, p\_2, \dots, p\_k$ .

예제1

예제 1
입력
```
3 30
2 3 7
```
예상 출력
```
28
```