Towers
Национална Студентска Олимпиада, 2013
Time Limit: 0.2s, Memory Limit: 64MiB
Towers Example Ели е отново на бойното поле! Тя е акустирала на брега на врага и иска да стигне до противниковата база, която се намира навътре в континента. За нейн ужас, както от лявата така и от дясната страна има високи планини, които тя не може да премине, а промеждутъкът между тях е осеян с N вражески кули. За простота можем да си представим пространството между планините като ивица с широчина W, в която са разположени N точки с целочислени координати (кулите).

Всяка кула има определен брой Ai войници в себе си. Колкото повече хора има в една кула, толкова по-ефективна е тя за отбрана. Ели е изчислила, че ако в една кула има X човека, то нейният обсег е X*X метра – тоест тя трябва да се придвижва на разстояние, стриктно по-голямо от X*X метра от кулата. Макар и обсегът на кулите да не стига до брега (тоест Ели може да се движи свободно по цялата му широчина), е възможно те да са така разположени, че момичето да не може да премине ивицата без да навлезе в обсега на някоя от тях.

За щастие, Ели е донесла със себе си своя снайпер, след всеки изстрел на който един войник по-малко ще й прави проблеми. Така тя може да обезвреди произволен брой войници от всяка от кулите (включително нито един или всички такива). Например, ако дадена кула е имала 5 войника, тоест е била с обсег 5 * 5 = 25 метра, тя може да отстрани двама от тях, като така намалява обсега на кулата до едва 3 * 3 = 9 метра.

Стрелянето със снайпера й отнема време, а изпълняването на мисията й възможно най-бързо е от критична важност. Сега тя се чуди какъв е най-малкият брой войници, които трябва да обезвреди, за да може да мине между кулите незабелязано.
Вход
На първия ред на стандартния са зададени целите числа N и W – съответно броя кули и широчината на ивицата. Следват N на брой реда, всеки от които съдържа по три цели числа Xi Yi Ai – съответно координатите на кулата и броя войници в нея, където Xi е разстоянието от лявата планина. Можете да считате, че плажът се намира достатъчно на юг (примерно с големи отрицателни Y координати), така че обзорът на никоя кула да не стига до там.
Изход
За всеки пример изведете по един ред на стандартния изход, съдържащ едно цяло число – минималния брой войници, които трябва да отстрани Ели, за да може да премине през ивицата. Забележете, че това винаги е възможно, ако например тя премахне всички войници.
Ограничения
  • 1 ≤ N ≤ 30
  • 1 ≤ Ai ≤ 200
  • 3 ≤ W ≤ 1000
  • 1 ≤ XiW
  • 1 ≤ Yi ≤ 1000
Примерен Вход Примерен Изход
3 6 1 8 2 3 8 2 5 8 2 3
9 20 1 5 5 1 10 4 5 4 3 5 11 5 15 3 4 15 9 3 19 1 2 19 8 2 19 17 2 10
1 8 4 4 10 9
Едно възможно решение в първия пример е да се намали броя войници в първата кула до нула, а във втората – до един.
Мрън!