eolymp
bolt
Try our new interface for solving problems
Problems

Волчьи тропы

Волчьи тропы

Time limit 2 seconds
Memory limit 64 MiB

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

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

  • Скалу Советов следует оборудовать только в центре квадрата;

  • между каждыми двумя Скалами должен существовать ровно один простой путь, состоящий из одной или нескольких тропинок;

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

  • между двумя Скалами можно проложить тропинку, если расстояние между этими двумя Скалами не больше k;

  • если между двумя Скалами существует более чем 10^{6 }вариантов кратчайшей тропинки, то считаем, что между двумя этими Скалами существует ровно 10^{6 }тропинок.

  • Между каждыми двумя Скалами должен существовать ровно один не самопересекающийся путь по проложенным тропинкам.

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

Input data

В первой строке записаны два числа n (1n80) и k (0k10^18) - количество Скал Советов и максимальное допустимая длина тропинки. Следующие n строк содержат координаты Скал Советов (все координаты лежат в диапазоне от 0 до 10^18).

Output data

Выведите количество различных вариантов проложить тропинки между Скалами Советов.

Examples

Input example #1
5 2
0 0
1 1
2 2
3 3
4 4
Output example #1
16
Source 2010 VII Открытый Чемпионат Харькова, I дивизион, 28 ноября, Задача J