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

დროის ლიმიტი: 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