საიუველირო მაღაზია

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

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

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

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

წყარო: COCI, 2013/14, #1


მირკომ გადაწყვიტა, საიუველირო მაღაზია გაძარცვოს. მაღაზიაში არის N ცალი სამკაული, რომელთაგან, თითოეულის წონაა Mi და ფასი - Vi. მირკოს აქვს K ცალი ჩანთა, რომელთაგან თითოეულს შეუძლია დაიტიოს მაქსიმუმ Ci წონის სამკაული. მირკოს სურს, რომ თითოეულ ჩანთაში მოათავსოს არაუმეტეს თითო სამკაულისა, რათა უნებურად მათ ერთმანეთი არ დააზიანონ. იპოვეთ სამკაულების მაქსიმალური ჯამური ფასი, რომლის წაღებაც შეუძლია მაღაზიიდან მირკოს.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი დადებითი რიცხვი N და K (1 ≤ N, K ≤ 300 000). მომდევნო N სტრიქონიდან თითოეულში ორ-ორი მთელი დადებითი რიცხვი Mi და Vi (1 ≤ Mi , Vi ≤ 1 000 000). მომდევნო K სტრიქონიდან თითოეულში თითო მთელი დადებითი რიცხვი Ci (1 ≤ Ci ≤ 100 000 000). 

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

 




მაგალითები

შესატანი მონაცემები
2 1 5 10 100 100 11 დაკოპირება
გამოსატანი მონაცემები
10 დაკოპირება
შესატანი მონაცემები
3 2 1 65 5 23 2 99 10 2 დაკოპირება
გამოსატანი მონაცემები
164 დაკოპირება