Ели е отново на бойното поле! Тя е акустирала на брега на врага и иска да стигне до противниковата база, която се намира навътре в континента. За нейн ужас, както от лявата така и от дясната страна има високи планини, които тя не може да премине, а промеждутъкът между тях е осеян с N вражески кули. За простота можем да си представим пространството между планините като ивица с широчина W, в която са разположени N точки с целочислени координати (кулите).

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

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

Стрелянето със снайпера й отнема време, а изпълняването на мисията й възможно най-бързо е от критична важност. Сега тя се чуди какъв е най-малкият брой войници, които трябва да обезвреди, за да може да мине между кулите незабелязано. На първия ред на стандартния са зададени целите числа N и W – съответно броя кули и широчината на ивицата. Следват N на брой реда, всеки от които съдържа по три цели числа X_i Y_i A_i – съответно координатите на кулата и броя войници в нея, където X_i е разстоянието от лявата планина. Можете да считате, че плажът се намира достатъчно на юг (примерно с големи отрицателни Y координати), така че обзорът на никоя кула да не стига до там. За всеки пример изведете по един ред на стандартния изход, съдържащ едно цяло число – минималния брой войници, които трябва да отстрани Ели, за да може да премине през ивицата. Забележете, че това винаги е възможно, ако например тя премахне всички войници.

• 1 ≤ N ≤ 30
• 1 ≤ A_i ≤ 200
• 3 ≤ W ≤ 1000
• 1 ≤ X_i ≤ W
• 1 ≤ Y_i ≤ 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