Towers
Национална Студентска Олимпиада, 2013
Time Limit: 0.5s, Memory Limit: 64MiB

Всяка кула има определен брой 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 ≤ Xi ≤ W
- 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 |
Едно възможно решение в първия пример е да се намали броя войници в първата кула до нула, а във втората – до един.