시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB246595717402022.275%

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

힌트

두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

W3sicHJvYmxlbV9pZCI6IjEyMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHViM2M0XHViNDUxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzhcdWFjYzRcdWM4MDFcdWM3NzggXHViM2M0XHViNDUxIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM4MTBcdWM3NDQgXHVkMTM4XHVhZTMwXHViODVjIFx1YWNiMFx1YzJlY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1ZDEzOCBcdWJjZjRcdWMxMWRcdWM4MTBcdWM1ZDBcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzc0IFx1Y2QxZCBOXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YmNmNFx1YzExZFx1Yzc0MCBcdWJiMzRcdWFjOGMgTTxzdWI+aTxcL3N1Yj5cdWM2NDAgXHVhYzAwXHVhY2E5IFY8c3ViPmk8XC9zdWI+XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWFjMDBcdWJjMjlcdWM3NDQgS1x1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVhYzAwXHViYzI5XHVjNWQwIFx1YjJmNFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWJiMzRcdWFjOGNcdWIyOTQgQzxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuIFx1YWMwMFx1YmMyOVx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWJjZjRcdWMxMWRcdWI5Y2MgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWQ2ZDRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBLICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJjZjRcdWMxMWRcdWM3NTggXHVjODE1XHViY2Y0IE08c3ViPmk8XC9zdWI+XHVjNjQwIFY8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAmbmJzcDsmbGU7IE08c3ViPmk8XC9zdWI+LCBWPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMFx1YmMyOVx1YzVkMCBcdWIyZjRcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHViYjM0XHVhYzhjIEM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHVkNmQ0XHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViY2Y0XHVjMTFkJm5ic3A7XHVhYzAwXHVhY2E5XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJjZjRcdWMxMWRcdWM3NDQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFjMDBcdWJjMjlcdWM1ZDAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHViY2Y0XHVjMTFkXHVjNzQ0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhYzAwXHViYzI5XHVjNWQwIFx1YjEyM1x1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMjAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTE9QT1YiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBkaWZmaWN1bHQgZWNvbm9taWMgc2l0dWF0aW9uIGluIHRoZSBjb3VudHJ5IGFuZCByZWR1Y3Rpb25zIGluIGdvdmVybm1lbnQgYWdyaWN1bHR1cmFsIHN1YnNpZHkgZnVuZGluZyBoYXZlIGNhdXNlZCBNaXJrbyB0byBjaGFuZ2UgaGlzIGNhcmVlciBhZ2FpbiwgdGhpcyB0aW1lIHRvIGEgdGhpZWYuIEhpcyBmaXJzdCBwcm9mZXNzaW9uYWwgZW5kZWF2b3VyIGlzIGEgamV3ZWxsZXJ5IHN0b3JlIGhlaXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc3RvcmUgY29udGFpbnMgTiBwaWVjZXMgb2YgamV3ZWxsZXJ5LCBhbmQgZWFjaCBwaWVjZSBoYXMgc29tZSBtYXNzIE08c3ViPmk8XC9zdWI+IGFuZCB2YWx1ZSBWPHN1Yj5pPFwvc3ViPi4gTWlya28gaGFzIEsgYmFncyB0byBzdG9yZSBoaXMgbG9vdCwgYW5kIGVhY2ggYmFnIGNhbiBob2xkIHNvbWUgbWF4aW11bSBtYXNzIEM8c3ViPmk8XC9zdWI+LiBIZSBwbGFucyB0byBzdG9yZSBhbGwgaGlzIGxvb3QgaW4gdGhlc2UgYmFncywgYnV0IGF0IG1vc3Qgb25lIGpld2VsbGVyeSBwaWVjZSBpbiBlYWNoIGJhZywgaW4gb3JkZXIgdG8gcmVkdWNlIHRoZSBsaWtlbGlob29kIG9mIGRhbWFnZSBkdXJpbmcgdGhlIGVzY2FwZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbWF4aW11bSB0b3RhbCBqZXdlbGxlcnkgdmFsdWUgdGhhdCBNaXJrbyBjYW4gJmxkcXVvO2xpYmVyYXRlJnJkcXVvOy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBudW1iZXJzLCBOIGFuZCBLICgxICZsZTsgTiwgSyAmbGU7IDMwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHBhaXIgb2YgbnVtYmVycywgTTxzdWI+aTxcL3N1Yj4gYW5kIFY8c3ViPmk8XC9zdWI+ICgwICZsZTsgTTxzdWI+aTxcL3N1Yj4sIFY8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEsgbGluZXMgY29udGFpbnMgYSBudW1iZXIsIEM8c3ViPmk8XC9zdWI+ICgxICZsZTsgQzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAgMDAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsbCBudW1iZXJzIGluIHRoZSBpbnB1dCBhcmUgcG9zaXRpdmUgaW50ZWdlcnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWF4aW11bSBwb3NzaWJsZSB0b3RhbCBqZXdlbGxlcnkgdmFsdWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBzZWNvbmQgZXhhbXBsZTogTWlya28gc3RvcmVzIHRoZSBmaXJzdCBwaWVjZSBvZiBqZXdlbGxlcnkgaW50byB0aGUgc2Vjb25kIGJhZyBhbmQgdGhlIHRoaXJkIHBpZWNlIGludG8gdGhlIGZpcnN0IGJhZy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #1 4번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: eeight