წველის განრიგი

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

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

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

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

წყარო: USACO, 2013/14, DEC, SILVER


ფერმერ ჯონი წველის N (1 <= N <= 10,000) ძროხას. ყოველი ძროხის მოწველას ის დროის ერთ ერთეულს ანდომებს. ძროხები მოუთმენლად თავის რიგს ელოდებიან, და თუ რიგში ყოფნა ზედმეტი უწევთ, მაშინ მოწველაზე უარს ამბობენ. კერძოდ, ძროხა i იძლევა რძის g_i (1 <= g_i <= 1000) ლიტრს მხოლოდ მაშინ, თუ რიგში ლოდინი ნაკლებია d_i (1 <= d_i <= 10,000) -ზე. დროის ათვლა იწყება მომენტში t=0. შედეგად t=x დროის მომენტამდე მოიწველება x ძროხა. გათვალეთ, ჯამში რძის მაქსიმუმ რამდენ ლიტრს მოწველის ჯონი, თუ ის ოპტიმალურად იმოქმედებს.

შემავალი მონაცემების ფორმატი:

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

  • სტრიქონები 2..1+N: მოიცავენ ორ მთელს g_i და d_i.

გამომავალი მონაცემების ფორმატი:

* სტრიქონი 1: მოწველილი რძის მაქსიმალური ჯამური რაოდენობა.




მაგალითები

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

შენიშვნა

მოცემულია 4 ძროხა. პირველი იძლევა 10 ლიტრ რძეს, თუ მოლოდინის დრო ნალებია 3-ზე და ა.შ. პირველად ჯონი მოწველის მე-3 ძროხას, და ამის შედეგად გამოტოვებს მე-4 ძროხას. შემდეგ მოიწველება ძროხები 1 და 2.