Lopov

LOPOV

Ülkedeki güç ekonomik şartlar ve hükümetin tarımsal desteği kesmesi Mirko'yu mesleğini değiştirmeye iter, artık bir hırsızdır.Elmas çalma işindedir.

Bir depoda N tane elmas parçası , ve her elmasın Mi

ağırlığı ve Vi değeri vardır.

Mirko'nun ise K tane torbası ve her torbanın Ci maksimum kapasitesi vardır.

Bütün çaldıklarını bu torbada taşıyacaktır fakat elmaslara zarar gelmemesi için her torbada yalnız bir elmas taşıma hakkı vardır.

Mirko'nun çalabileceği toplam maksimum elmas değerini bulunuz.

GİRDİ

İlk satırda iki sayı, N ve K (1 ≤ N, K ≤ 300 000).

Ardından gelen N satırda ikişer sayı vardır, Mi ve Vi (1 ≤ Mi, Vi≤ 1 000 000).

Geri kalan K satırda bir sayı, Ci (1 ≤ Ci ≤ 100 000 000).

Girdideki tüm sayılar pozitiftir.

ÇIKTI

Tek satırda Mirko'nun taşıyabiliceği maksimum toplam elmas değeri.

Dataların %50'sinde N ve K 5000'i aşmıyacaktır.

Örnek Girdi-Çıktılar

girdi

2 1

5 10

100 100

11

çıktı

10

girdi

3 2

1 65

5 23

2 99

10

2

çıktı

164

Çözüm:

Soruyu çözerken bulmak istediğimiz şey, her bir çanta için kendi ağırlığına eşit veya kendi ağırlığından küçük ağırlığı olan ve en büyük değere sahip elması bulmak. Bunun için de çantaları küçükten büyüğe, elmasları da ağırlığına göre küçükten büyüğe sıralıyoruz.

Sonra 1'den N'e doğru her bir çanta için sıradaki işlemleri yapacağız:

1- O çantanın içine sığabilecek ağırlıktaki tüm elmasların değerlerini max heap'e atacağız (Eğer daha önce atılmamışsa).

2- Sonra heap'ten ilk elemanı alarak o çantanın içine koyarak heap'ten çıkartırız.

3- Çantaya koyduğumuz değeri toplama ekleriz.

Bu işlemi en büyük çanta için de yaptığımızda dolabilecek olan bütün çantalar optimum şekilde dolmuş olur ve sonuca ulaşmış oluruz.

Soru : http://www.hsin.hr/coci/contest1_tasks.pdf

Girdi-Çıktı: http://www.hsin.hr/coci/contest1_testdata.zip

İngilizce Çözüm: http://www.hsin.hr/coci/contest1_solutions.zip