Короткое название

Цветочный луг представляет собой квадрат на координатной плоскости с левым нижним углом в точке (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) во входных данных различны.