← К списку задач

Обезвреживание бомбы

Сложность: 15%

В городе Найт-Сити творится много страшных событий. Прямо сейчас Ви рискует жизнью, чтобы обезвредить бомбу в самом центре региона Уотсон.

Быстро изучив бомбу, Ви заметил, что на ней есть ровно nn кнопок, на каждой из которых написано натуральное число. Любая кнопка может быть в активном и неактивном состоянии, переключение состояния происходит по нажатию, которое занимает ровно одну секунду. Изначально все кнопки находятся в активном состоянии.

От доверенного информатора Ви знает, что бомба взорвется если и только если на момент конца обратного отчета на ней найдутся две кнопки в активном состоянии с суммой чисел на них ровно kk. Разумеется, его интересует, за какое минимальное время бомбу можно обезвредить.

Свой мозговой имплант для быстрых вычислений Ви повредил на прошлом задании, и теперь ему нужна ваша помощь, чтобы узнать какое минимальное количество нажатий кнопок придется совершить, чтобы бомба не взорвалась.

Входные данные

В первой строке даны два целых числа nn и kk (1n105,1k1091 ⩽ n ⩽ 10^5, 1 ⩽ k ⩽ 10^9).

В следующей строке даны nn чисел, которые написаны на кнопках (1ai1091 ⩽ a_i ⩽ 10^9).

Выходные данные

Выведите единственное число — минимальное количество нажатий на кнопки, необходимое для обезвреживания бомбы.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадачи

баллынеобх. подзадачиограничения
1

20

-

n20n ⩽ 20

2

30

-

n,ai,k1000n, |a_i|, k ⩽ 1 000

3

50

1, 2

Без дополнительных ограничений

STDINSTDOUT
5 100
77 23 45 54 22
1
7 7
4 3 4 8 4 3 4
2