სამუშაოს დაგეგმვა

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

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

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

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

წყარო: USACO, 2008/09, OPEN, GOLD


ფერმერს ჯონს ბევრი საქმე დაუგროვდა გასაკეთებელი. იმისთვის, რომ მან წარმატებულად მართოს ფერმა, ფული უნდა გამოიმუშავოს. ის თითოეულ სამუშაოს დროის 1 ერთეულში ასრულებს.

მისი სამუშაო დღე იწყება დროის 0 მომენტში და აქვს 1,000,000,000 დროის ერთეული. მას ასარჩევად აქვს N (1 <= N <= 100,000) სამუშაო, რომლებიც გადანომრილია 1..N. შესაძლებელია, თუმცა ნაკლებ სავარაუდოა, რომ მან შეძლოს ყველა სამუშაოს შესრულება, რადგან თითოეულ სამუშაოს გააჩნია დედლაინი და ისინი შეიძლება ერთმანეთს დაემთხვეს.

i-ურ სამუშაოს აქვს D_i (1 <= D_i <= 1,000,000,000) დედლაინი და P_i (1 <= P_i  <= 1,000,000,000) შემოსავალი თუკი მას შეასრულებს.

რა არის მაქსიმალური შემოსავალი რასაც ფერმერ ჯონი მიიღებს მოცემული სამუშაოების დროს?

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

*         პირველი სტრიქონი: ერთი რიცხვი N.

*         2..N+1 სტრიქონები: i+1-ე სტრიქონი შეიცავს 2 ჰარით დაშორებულ რიცხვს: D_i და P_i.

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




მაგალითები

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