Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
У овом задатку опустићемо се од ужурбаног градског живота и бавити се коњима и шталама. Тренутно обилазите фарму коју представља дводимензионална раван са шталама које представљају тачке у овој равни. Ви сте на коњу који много воли цео број \(c\) и у једном кораку може прећи дуж од тачке \((x,y)\) до \((x+ac,y+bc)\), где \(a,b \in \{-1,0,1\}\) (дакле, може отићи \(c\) поља у лево, десно, горе или доле, као и “по дијагонали”). Уколико се нека штала нађе на путу коња (на крајевима ове дужи или негде на њој), сматрамо да смо је обишли. Желимо да знамо колико највише штала можемо обићи ако крећемо из произвољне штале од оних датих у улазу (није важан број корака, нити ико брани коњу да више пута буде у истој тачки).
У првом реду дати су размаком раздвојени бројеви \(n\) и \(c\) (\(n\) је број штала, а \(c\) омиљени број коња). Затим се уносе \(n\) редова, и у \(i\)-том од њих дати су размаком раздвојени цели бројеви \(x_i\) и \(y_i\), који представљају \(x\) и \(y\) координату \(i\)-те штале (никоје две штале се не преклапају).
У једином реду излаза потребно је исписати тражени резултат.
4 3
0 0
0 5
6 4
2 14Ако кренемо од штале \((0,5)\), у два корака стижемо до \((0,-1)\), крећући се дуж \(y\) осе, тако пролазећи кроз прву шталу. На дијагонали од \((0,-1)\) до \((3,2)\) налази се и штала \((2,1)\), те тако њу обиђемо. Сада смо у \((3,2)\) и идемо у једном кораку до \((6,2)\) крећући се “на десно” док онда одемо “на горе” и дођемо до \((6,5)\), прошавши кроз последњу шталу, чиме је наш обилазак свих 4 штала завршен.
5 4
1 1
1 6
4 12
-1 0
-1 -24Примери су подељени у 5 дисјунктних група: - У тест примерима вредним 15 поена: \(n \leq 8\) - У тест примерима вредним 25 поена: \(n \leq 18\) - У тест примерима вредним 10 поена: \(c = 2\) - У тест примерима вредним 25 поена: \(n \leq 2000\) - У тест примерима вредним 25 поена: нема додатних ограничења