Lopov
레이팅 미적용의견: 0
\(1^{st}\) round, September \(28^{th}\), 2013
The difficult economic situation in the country and reductions in government agricultural subsidy
funding have caused Mirko to change his career again, this time to a thief. His first professional
endeavour is a jewellery store heist.
The store contains N pieces of jewellery, and each piece has some mass M_{i} and value V_{i}. Mirko has K
bags to store his loot, and each bag can hold some maximum mass C_{i}. He plans to store all his loot in
these bags, but at most one jewellery piece in each bag, in order to reduce the likelihood of damage
during the escape.
Find the maximum total jewellery value that Mirko can “liberate”.
In test data worth at least 50% of total points, N and K will be less than 5000.
The first line of input contains two numbers, N and K (\(1 \le N\), \(K \le 300\,000\)).
Each of the following N lines contains a pair of numbers, M_{i} and V_{i} (\(1 \le M_{i}\), \(V_{i} \le 1\,000\,000\)).
Each of the following K lines contains a number, C_{i} (\(1 \le C_{i} \le 100\,000\,000\)).
All numbers in the input are positive integers.
The first and only line of output must contain the maximum possible total jewellery value.
2 1
5 10
100 100
11103 2
1 65
5 23
2 99
10
2164Clarification of the second example: Mirko stores the first piece of jewellery into the second bag and
the third piece into the first bag.
평가 및 의견
Lopov
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Lopov