XIII конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

Горски шашки
Голямата гора отново е обзета от спортна треска: предстои ежегодният турнир по Горски шашки – царя на всички горски спортове. Състезанието се очертава да бъде доста интересно. Миналогодишният шампион няма да участва поради стомашни проблеми, а опасенията претендентите да го изместят от трона нарастват с всеки изминал ден.
Докато почти всички горски обитатели тръпнат в очакване, приятелите на Мечо Пух подготвят хитър план. По традиция на турнирите по Горски шашки всеки състезател има на разположение специална лична стая с мед, където да може да остава насаме по всяко време на играта. Естествено няма начин Пух да пропусне такава възможност, поради което той всяка година участва в турнира. Бухал обаче е измислил как може да подсказва на Мечо в личната стая. Сега остава само да им напишете програма, с която да намират най-добрите ходове.
Играта Горски шашки произлиза от шаха. Легендата обяснява избора на името шашки вместо шах с това, че когато митичната горска риба Боби за първи път видяла играта, много се шашнала. Играе се на квадратно шахматно табло с размери M на M (М<100 000). Всички фигури, наричани „пони“, произлизат от шахматния топ, като всяка от тях се характеризира с едно число L (0<9), което показва, че за един ход може да се премести точно L полета по вертикала или по хоризонтала. Едно пони заплашва друго за K хода, когато може да се премести върху него с не повече от K хода, като по пътя си може да стъпва и върху други фигури.
Програмата, от която Бухал се нуждае, трябва да решава следната задача за не повече от 6 секунди. При дадена конфигурация на дъска да сметне колко понита заплашва всяко едно от тях в рамките на K (0<К<100 000) хода и да изведе сумата от намерените стойности.
Вход
На първия ред на файла CHECKERS.INP ще има две цели чис- ла N (1<200 000) и K. На всеки от следващите N реда ще има по три цели числа Xi Yi Li, показващи позицията (0(0<Xi, Yi) и полетата, които изминава за един ход i-тото пони. Не може да има две или повече понита на една и съща позиция.
Изход
На единствения ред на файла CHECKERS.OUT трябва да изведете едно цяло число – търсената сума.
Пример

В първия случай понитата (в реда, в който са във входния файл) могат да вземат съответно по 0+1+1=2 фигури, а във втория по 2+2+1+0=5 фигури.
Забележка
Понитата не са разделени на цветове. Докато едно пони прави K хода, за да вземе друго пони, останалите фигури не се местят. Решенията на задачата може да изпратите чрез системата за upload директно на сайта http://konkurs.musala.com  до 10 април 2008 г.