ვაშლის მოსავალი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2002/03, FALL, GREEN


ზაფხულში ძროხები საყვარელი ხილის, ვაშლის მოსავალს იღებენ. ფერმერ ჯონის ფერმაზე ვაშლები განსაკუთრებული წესით იკრიფება. ძროხა ბესი დაარხევს ხეს, ხოლო ჯონი იჭერს ვაშლებს. ფერმერი ჯონი ცდილობს დაიჭიროს რაც შეიძლება მეტი ვაშლი. მათი საერთო რაოდენობაა N (1<=N<=5,000).

ჯონი გამოცდილია ამ საქმიანობაში. მას შედგენილი  აქვს ბაღის შემოვლის ისეთი გეგმა, რომ  გაუფრთხილდეს  თითოეულ   დაგდებულ  ვაშლს.  მან  ზუსტად  იცის სად (კოორდინატები X, Y ეკუთვნიან დიაპაზონს  -1,000..1,000) და როდის (დრო T მდებარეობს დიაპაზონში 1 <=T<=1,000,000)  ვარდება  ყოველი ვაშლი. მან უნდა ისე შემოიაროს ბაღი, რომ მაქსიმალურად არ აცალოს ვაშლებს მიწაზე დავარდნა. ჯონს შეუძლია იაროს სიჩქარით S (1<=S<=1,000).  მხოლოდ  პოზიციიდან  (0,0)  პოზიციაში (1,1) ჯონი გადადის დროის ზუსტად 1.41 ერთეულში.  მაქსიმალურად რა რაოდენობის ვაშლის დაჭერას ის მოახერხებს, თუ გამოსვლის წინ მისი ადგილმდებარეობის კოორდინატებია (0,0).

შესატანი მონაცემები:

* სტრიქონი 1: შეიცავს ღარით გამოყოფილ ორ მთელს N და S.

* სტრიქონები 2..N+1: თითოეული შეიცავს ჰარით გამოყოფილ 3  ცალ მთელს Xi, Yi  და  Ti ვაშლის ვარდნის დეკარტეს კოორდინატებსა და დროს.

გამოსატანი მონაცემები:

ერთი სტრიქონი ერთი მთელი რიცხვით, რომელიც აღნიშნავს ვაშლების იმ მაქსიმალურ რაოდენობას, რომელთა დაჭერის მოსწრებას მოახერხებს ჯონი.

 




მაგალითები

შესატანი მონაცემები
5 3 0 0 1 0 3 2 -5 12 6 -1 0 3 -1 1 2 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

ჯონს შეუძლია დაიჭიროს ვაშლები 1, 5 და 4