აკრობატი ძროხები

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

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

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

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

წყარო: USACO, 2005/06, NOV, SILVER


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

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

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

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

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

* სტრიქონები 2..N+1: ორ-ორი მთელი რიცხვი W_i და S_i.

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

სტრიქონი 1: ერთი მთელი რიცხვი, ყველა ძროხას შორის უდიდესი რისკის მინიმალური მნიშვნელობა.




მაგალითები

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

შენიშვნა

ყველაზე ქვემოთ დადგება ძროხა, წონით 10. მისი წაქცევის რისკი იქნება 2+3-3=2. დანარჩენი 2 ძროხის რისკი უფრო მცირეა.