F. Казак Ус и конфеты

Казак Вус обожает прыгать и собирать конфеты. Однажды он оказался на числовой прямой, где в некоторых целочисленных точках лежат конфеты (в каждой точке не более одной конфеты). Вус был в восторге и решил собрать как можно больше конфет. Для этого он может выбрать любое целое число x > 1 и начальную позицию s (где s — целое число), после чего он будет прыгать на расстояние x и посещать все точки вида s+kx, где k — неотрицательное целое число. Если Вус попадает в точку с конфетой, он подбирает её (хотя так делать нельзя!).

Помогите Вусу собрать максимальное количество конфет.

Протокол взаимодействия

Вам необходимо реализовать функцию:

integer solve(integer n, integer g, array of integers m)

• n — количество конфет;

• g — номер блока;

• m — массив, содержащий позиции конфет;

• функция должна возвращать одно целое число — максимальное количество конфет, которое может собрать Вус.

Формат входных данных

Первая строка содержит два целых числа n и g (1 ⩽ n ⩽ 10^5; 0 ⩽ g ⩽ 6) — количество конфет и номер блока соответственно.

Вторая строка содержит n целых чисел a[1], a[2], ..., a[n] (1 ⩽ a[i] ⩽ 10^9) — позиции, в которых находятся конфеты. Гарантируется, что все ai различны.

Формат выходных данных

Выведите одно целое число — максимальное количество конфет, которое сможет собрать Вус.

Примеры

Примечание

В первом примере Казак может выбрать x = 2 и собрать конфеты на позициях 1, 3 и 7.Во втором примере Казак может выбрать x = 3 и собрать конфеты на позициях 1, 4, 7, 10 и 13.

Оценивание

1. (4 балла) n ⩽ 2; a[i] ⩽ 10;

2. (5 баллов) n ⩽ 3; a[i] ⩽ 10^2;

3. (12 баллов) n ⩽ 10; a[i] ⩽ 10^2;

4. (20 баллов) n ⩽ 10^3; a[i] ⩽ 10^4;

5. (25 баллов) n ⩽ 10^4; a[i] ⩽ 10^6;

6. (34 балла) без дополнительных ограничений.