კომუნიკაციის სისტემა

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

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

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

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

წყარო: USACO, 2016/17, DEC, SILVER


ფერმერ ჯონის N ძროხამ (1N200) გადაწყვიტა კომუნიკაციის სისტემის შემუშავება, რათა მნიშვნელოვანი ინფორმაცია გადააწოდონ ერთმანეთს. ძროხებმა შეიძინეს სპეციალური აპარატები (თითოეულს ზუსტად ერთი აპარატი). თითოეულ აპარატს აქვს თავისი P სიძლიერე და შეუძლიათ ინფორმაციის გადაწოდება მაქსიმუმ P მანძილზე. სამაგიეროდ ძროხებს შეუძლიათ ჯაჭვურად გადააოწოდონ ერთმანეთს ინფორმაცია. A - > B - ... -> C. რადგან ძროხებს შეიძლება განსხვავებული სიძლიერის აპარატები ჰქონდეთ, ისინი სხვადასხვა რაოდენობის ძროხებთან შეძლებენ დაკავშირებას. ამოცანა მოითხოვს მოძებნოთ მაქსიმალური ძროხების რაოდენობა, რომლებთანაც რომელიმე ერთი ძროხა შეძლებს დაკავშირებას.

 

შეტანის ფორმატი:

პირველი ხაზი შეიცავს N-ს. შემდეგი N ხაზიდან თითოეული შეიცავს x და y-ს რომლებიც აღნიშნავენ ძროხის კოორდინატებს (ინტერვალში 025,000) რასაც მოყვება რიცხვი p, აპარატის სიძლიერე.

 

გამოტანის ფორმატი:

ერთ ხაზში გამოიტანეთ მაქსიმალური რაოდენობა რომლებთანაც რომელიმე ძროხა შეძლებს დაკავშირებას.

 

 



მაგალითები

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