დროის ლიმიტი: 5 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
ბუბა მსხვილი ბიზნესმენია და მას მთელი მსოფლიოდან აქვს შეკვეთები ეგზოტიკური ქართული ყველის "ჩეჩილის" გაგზავნაზე. ბუბას შეეძლო ერთდროულად 10-ზე მეტ შეკვეთაზე ემუშავა, მაგრამ ვირუსული პანდემიის გამო იძულებული გახდა შეემცირებინა თანამშრომლების რაოდენობა საწარმოში და ახლა დღეში მხოლოდ ერთი შეკვეთის შესრულება შეუძლია. მას აქვს N (1<=N<=1000000) ცალი შეკვეთა, რომელთაგან თითოეული ხასიათდება ორი პარამეტრით: გაგზავნის ვადა (დღეების რაოდენობა, რომელსაც არ უნდა გადაცილდეს შეკვეთის შესრულება) და ჯარიმა, რომელიც დაეკისრება ბუბას საწარმოს, თუკი შეკვეთის შესრულება დანიშნულ დროს გადააცილა. დაწერეთ პროგრამა, რომელიც განსაზღვრავს შეკვეთების შესრულების ისეთ თანმიმდევრობას, რომლის დროსაც ჯარიმების ჯამური რაოდენობა მინიმალური იქნება.
შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი N - შეკვეთების რაოდენობა. მეორე სტრიქონში N ცალი მთელი რიცხვი - თითოეული შეკვეთის შესრულების ვადა. მესამე სტრიქონში N ცალი მთელი რიცხვი - ჯარიმა შესაბამისი შეკვეთის დროულად შეუსრულებლობისათვის.
გამოსატანი მონაცემები: ერთი მთელი რიცხვი - ჯარიმების ჯამური მინიმალური რაოდენობა.
შესატანი მონაცემები
11 8 6 4 3 5 1 3 6 9 4 5 30 10 50 50 70 15 40 20 40 25 30 დაკოპირება
გამოსატანი მონაცემები
50 დაკოპირება
ვერ მოხერხდება მეორე, მეექვსე და მეცხრე შეკვეთების დროულად შესრულება, ამიტომ ჯარიმების ჯამია 10+15+25=50. სხვა შემთხვევებში ჯარიმების ჯამი მეტი იქნებოდა.