Задача B. Зельеварение

Автор:Н. Ляхута, М. Спорышев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Вася сварил N таких зелий, i-е зелье увеличивает температуру окружающей среды на целое число ai градусов. Каждое зелье он налил в отдельную колбу, чтобы зелья начали испаряться. Все колбы одинаковы. Эффекты от паров зелий в разных колбах складываются. Колбы Вася выставил в ряд и начал наблюдать за изменением температуры в комнате.

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T0 + K, где T0 — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

Помогите Васе определить, на какие колбы направить свои заклинания.

Формат входного файла

Первая строка входного файла содержит два целых числа N K —– количество колб с зельями и температура, на которую Вася хочет изменить исходную в комнате.

Вторая строка содержит N целых чисел, i-е число — количество градусов, на которое увеличится температура окружающей среды из-за паров i-ой колбы.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 2 ⋅ 103

107 ≤ K ≤ 107

104 ≤ ai ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0
1
1
2
5 1
1 2 3 -1 -1
4

0.042s 0.012s 15