კიბე

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

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

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

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

წყარო: IBSU, 2014, ზამთრის ოლიმპიადა, VII-IX


მოცემულია n საფეხურიანი კიბე. ჩვენს მიზანს კი ამ კიბეზე ასვლა წარმოადგენს. ჩვეულებრივ, ასვლის დროს ყოველ ბიჯზე შესაძლებელია მხოლოდ ერთი საფეხურით (უშუალოდ მომდევნო საფეხურზე) ზემოთ გადაადგილება. კიბის k რაოდენობის საფეხურიდან თითოეულზე მოთავსებულია წყლიანი ბოთლი, რომელშიც, ვთქვათ, x დეცილიტრი (1 დეცილიტრი ლიტრის მეათედის ტოლია) წყალია. თუ ასვლის დროს, როცა ასეთ საფეხურზე მოვხვდებით, ბოთლიდან წყალს მთლიანად დავლევთ (თუმცა აუცილებელი არაა მთლიანად დავლიოთ), ჩვენი ძალა იმდენად იზრდება, რომ მომდევნო ერთ ბიჯზე ერთბაშად x რაოდენობის საფეხურით შეგვიძლია ზემოთ გადაადგილება. თუ ამის შემდეგ წყალს ისევ არ დავლევთ, კვლავ ასვლის ჩვეულებრივ რეჟიმს ვუბრუნდებით. წყალი უფასოა და, შესაბამისად, მასში არაფერს არ ვიხდით. გარდა ამისა, თითოეულ ბოთლში წყლის განსხვავებული რაოდენობა შეიძლება იყოს. 

ცნობილია აგრეთვე, რომ კიბის j რაოდენობის საფეხურიდან თითოეულზე მოთავსებულია ბოთლი ენერგეტიკული სასმელით და თითოეულ ასეთ ბოთლშიც სასმელის განსხვავებული რაოდენობა შეიძლება იყოს. ვთქვათ, ერთ-ერთ მათგანში y დეცილიტრი სასმელია. თუ ჩვენ ამ ბოთლიდან დავლევთ, ვთქვათ, q (q<=y) დეცილიტრს, მომდევნო ერთ ბიჯზე ერთბაშად არაუმეტეს 2q რაოდენობის საფეხურით ზემოთ გადაადგილებას შევძლებთ. ხოლო, თუ ამის შემდეგ სასმელს აღარ დავლევთ, ისევ ასვლის ჩვეულებრივ რეჟიმს დავუბრუნდებით. განსხვავებით წყლისა, ენერგეტიკული სასმელი ფასიანია: ყოველი დალეული q  დეცილიტრისათვის q ლარი უნდა გადავიხადოთ. 

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

დაწერეთ პროგრამა, რომელიც დაადგენს საფეხურების იმ მინიმალურ რაოდენობას, რომლებიც უნდა ავიაროთ კიბეზე ასასვლელად და ამ საფეხურების ასავლელად საჭირო თანხის მინიმალურ რაოდენობას.

შესატანი მონაცემები: სტანდარტული შეტანის პირველ  სტრიქონში მოცემულია ერთი მთელი დადებითი n რიცხვი (n <= 120)  – კიბეზე საფეხურების რაოდენობა. მეორე სტრიქონში ჩაწერილია მთელი არაუარყოფითი k რიცხვი (0 <= k <= n) – იმ საფეხურების რაოდენობა, რომლებზეც წყლიანი ბოთლები დგას. მომდევნო k რაოდენობის სტრიქონიდან თითოეული შეიცავს მთელ დადებით რიცხვთა წყვილს - იმ საფეხურის ნომერს, რომელზედაც წყლიანი ბოთლი დგას და ამ ბოთლში არსებულ, დეცილიტრებში გამოსახულ წყლის რაოდენობას შესაბამისად. შემდეგ სტრიქონში მოცემულია მთელი არაუარყოფითი j რიცხვი (0 <= j <= n) – იმ საფეხურების რაოდენობა, რომლებზედაც დგას ბოთლები ენერგეტიკული სასმელით. მომდევნო j რაოდენობის სტრიქონიდან თითოეული შეიცავს ისევ მთელ დადებით რიცხვთა წყვილს - იმ საფეხურის ნომერს, რომელზედაც დგას ბოთლი ენერგეტიკული სასმელით და ამ ბოთლში არსებულ, დეცილიტრებში გამოსახულ ენერგეტიკული სასმელის რაოდენობას შესაბამისად.

ყველა სტრიქონში მონაცემები ერთმანეთისაგან თითო ჰარითაა გამოყოფილი.

გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში უნდა ჩაიწეროს ერთი ჰარით გამოყოფილი ორი მთელი რიცხვი - კიბეზე ასასვლელად საჭირო საფეხურების მინიმალური რაოდენობა და ამ საფეხურების ასავლელად საჭირო მინიმალური თანხა შესაბამისად.

შეზღუდვები:

• თითოეულ ბოთლში არსებული წყლის რაოდენობა 1 <= x <= 100;

• თითოეულ ბოთლში არსებული ენერგეტიკული სასმელის რაოდენობა 1 <= y <= 100;




მაგალითები

შესატანი მონაცემები
6 1 1 2 2 4 1 1 2 დაკოპირება
გამოსატანი მონაცემები
3 2 დაკოპირება
შესატანი მონაცემები
6 1 1 2 2 4 1 1 1 დაკოპირება
გამოსატანი მონაცემები
4 1 დაკოპირება