დროის ლიმიტი: 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.
გამომავალი მონაცემების ფორმატი:
* სტრიქონი 1: მოწველილი რძის მაქსიმალური ჯამური რაოდენობა.
შესატანი მონაცემები
4 10 3 7 5 8 1 2 1 დაკოპირება
გამოსატანი მონაცემები
25 დაკოპირება
მოცემულია 4 ძროხა. პირველი იძლევა 10 ლიტრ რძეს, თუ მოლოდინის დრო ნალებია 3-ზე და ა.შ. პირველად ჯონი მოწველის მე-3 ძროხას, და ამის შედეგად გამოტოვებს მე-4 ძროხას. შემდეგ მოიწველება ძროხები 1 და 2.