Олимпиадные задачи

Стратегический альянс (100 баллов)

Знаменитая компания «Gold&Silver Soft» анонсировала дату выпуска  долгожданной пошаговой стратегической игры «Герои NET». Игра происходит в средневековье – время бесконечных междоусобиц и доблестных рыцарей. Действия игры разворачиваются в
стране X. Страна X представляет собой квадратную таблицу, разбитую на MxM одинаковых квадратных секторов. Каждый сектор имеет свои координаты: номер строки и номер столбца в таблице. Строки нумеруются сверху вниз начиная с единицы, столбцы нумеруются слева направо начиная с единицы. 

Игра сетевая, то есть каждый игрок управляет собственным персонажем – рыцарем.  Игра является пошаговой, соответственно игроки по очереди делают ходы. За один ход персонаж может сделать не более K шагов. За каждый шаг персонаж может переместиться из сектора, в котором находится рыцарь, в соседний сектор. Два сектора с координатами
(X1, Y1) и (X2, Y2) называются соседними, если |X1 – X2| ≤ 1 и |Y1 – Y2| ≤ 1.

Если два рыцаря оказываются в одном и том же секторе,  то они могут вступить в единоборство, в результате которого игра для побежденного игрока будет окончена.  Для придания остроты игре разработчики придумали понятие «стратегический альянс». Стратегический альянс – это союз (договор) трех рыцарей о взаимопомощи, то есть каждый из трех рыцарей обязуется в случае нападения на союзника (другого рыцаря из союза) оказать свою военную поддержку. Однако для того, чтобы оказать военную поддержку своим союзникам, каждый рыцарь должен иметь возможность добраться до двух своих союзников не более чем за один ход.

Рисунок№1. Описание  первого примера.

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

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

Первая строка входного файла содержит три целых числа N (1 ≤ N ≤ 5000),  
M (1 ≤ M ≤ 109) и K (1 ≤ K ≤ 109).

Каждая из следующих N строк описывает расположение одного рыцаря и содержит координаты сектора, в котором он находится – числа Xi и Yi соответственно (1 ≤ Xi, Yi ≤ M). Никаких два рыцаря не находятся в одном секторе.

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

Выходной файл должен содержать одно число – максимальное количество союзов.

Тесты