GCD

Time limit4sMemory limit512 MB

Summary

Given an array of up to 1e5 integers up to 1e18, erase at most k elements to maximize the GCD of the remaining elements.

Level: Medium7 of 10
Topics: Number theory, Math, Probability
Solved: No attempts yet

Problem

You are given an array of integers $a_1, a_2, \ldots, a_n$ . Find the maximum possible greatest common divisor of all numbers in the array if you can erase no more than $k$ elements ( $k \le \frac{n}{2}$ ) from it.

Input

The first line contains two integers $n$ , the number of elements in the array, and $k$ , the maximum number of elements you can erase ( $2 \le n \le 10^5$ , $0 \le k \le \frac{n}{2}$ ). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the array $a$ ( $1 \le a_i \le 10^{18}$ ).

Output

Print the maximum possible greatest common divisor of all elements left in the array after erasing no more than $k$ elements.

Examples3

Example 1
Input
```
4 1
6 15 35 14
```
Expected output
```
1
```
Example 2
Input
```
4 2
6 15 35 14
```
Expected output
```
7
```
Example 3
Input
```
3 1
897612484786617600 5828 16027
```
Expected output
```
1457
```