Волчьи тропы
В диких Джунглях кроме сионийской стаи волков обитает ещё много племён Свободного Народа. У каждой стаи есть свои обычаи, свой вожак и своя Скала Советов. Вся территория Джунглей разбита на одинаковые квадраты, и каждому племени Свободного Народа определены квадраты, в которых они могут охотится. Однако, хоть и редко, бывает, что волки из одной стаи приходят на совет к другой стае.
Чтобы избежать конфликтов, которые могут возникнуть при попадании на чужую территорию, совет старейшин, состоящий из вожаков стай, решил определить тропинки, по которым можно безопасно добраться от одной Скалы Советов до другой. Решение старейшин было таким:
Скалу Советов следует оборудовать только в центре квадрата;
между каждыми двумя Скалами должен существовать ровно один простой путь, состоящий из одной или нескольких тропинок;
проложенная тропинка должна иметь кратчайшую длину и состоять из отрезков, которые соединяют центры соседних по ребру квадратов;
между двумя Скалами можно проложить тропинку, если расстояние между этими двумя Скалами не больше k;
если между двумя Скалами существует более чем 10^{6 }вариантов кратчайшей тропинки, то считаем, что между двумя этими Скалами существует ровно 10^{6 }тропинок.
Между каждыми двумя Скалами должен существовать ровно один не самопересекающийся путь по проложенным тропинкам.
Напишите программу, которая подсчитает, сколько же существует различных вариантов проложить тропинки между Скалами Советов.
Входные данные
В первой строке записаны два числа n (1 ≤ n ≤ 80) и k (0 ≤ k ≤ 10^18) - количество Скал Советов и максимальное допустимая длина тропинки. Следующие n строк содержат координаты Скал Советов (все координаты лежат в диапазоне от 0 до 10^18).
Выходные данные
Выведите количество различных вариантов проложить тропинки между Скалами Советов.