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