Цветочный луг

могу доплатить за срочность, очень нужно решение!

Цветочный луг

ограничение по времени на тест

1 секунда

ограничение по памяти на тест

256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Цветочный луг представляет собой квадрат на координатной плоскости с левым нижним углом в точке (1,1) и правым верхним углом в точке (300,300). В течение n дней на лугу вырастают цветы, по одному в каждый день, но только в одной координате. Для каждого из n дней даны координаты точки (xi,yi), в которой вырастает цветок. Вася хочет подарить своей подруге букет из k цветов. Он хочет приехать на луг в некоторый день, стартовать из некоторой целой точки луга и проехать на своем квадроцикле. Квадроцикл не отличается надежностью, поэтому во избежание неполадок Вася может задать ему одно направление, параллельное сторонам или диагоналям луга, и проехать от стартовой точки вдоль этого направления, собрав все уже выращенные цветы по дороге. Считается, что цветы никогда не вянут, то есть цветок, выращенный в день i, может быть собран как в день i, так и во все последующие. У Васи много дел, поэтому он может приехать на луг ровно в один день. Найдите самый ранний день, в который Вася может собрать букет из k цветов в соответствии с ограничениями передвижения его квадроцикла.

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

В первой строке заданы 2 натуральных числа n и k (1?k?n?10^4) — количество дней, в которые на лугу вырастает новый цветок, и требуемое количество цветов в букете.

В i-й из следующих n из следующих n строк заданы два натуральных числа Xi,Yi (1?xi,yi?300) — координаты точки, в которой вырастет цветок в i-й день. Дни нумеруются с единицы.

Гарантируется, что все пары (xi,yi) во входных данных различны.

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

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

Гарантируется, что такой день всегда существует, то есть если Вася приедет на луг в день n, он точно сможет собрать букет из k цветов.