შეკვეთები პანდემიის დროს

დროის ლიმიტი: 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. სხვა შემთხვევებში ჯარიმების ჯამი მეტი იქნებოდა.