LOPOV - Lopov


 

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 Mi
 and value Vi
. Mirko has K 
bags to store his loot, and each bag can hold some maximum mass Ci
. 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”. 

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 Mi and value Vi. Mirko has K bags to store his loot, and each bag can hold some maximum mass Ci. 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”. 

 

Input

The first line of input contains two numbers, N and K (1 ≤ N, K ≤ 300 000). 

Each of the following N lines contains a pair of numbers, Mi and Vi (1 ≤ Mi, Vi ≤ 1 000 000).

Each of the following K lines contains a number, Ci (1 ≤ Ci ≤ 100 000 000). 

All numbers in the input are positive integers. 

Output

The first and only line of output must contain the maximum possible total jewellery value. 

Example

Input:
 
2 1 
5 10 
100 100 
11 

Output:
10

Input:
 
3 2 
1 65 
5 23 
2 99 
10 
2 

Output:
164

hide comments
hodobox: 2016-07-10 16:32:18

AC O(nlogn + klogk) in 0.31

Pulkit Singhal: 2014-10-04 05:23:00

Easy One :) AC in O(nlogn+klogk)

you_know_why: 2014-05-14 03:48:25

TLE for (nlogn+nlogk) !!!

785227: 2014-04-05 17:53:15

Go greedy !!

Dario Sindicic: 2013-12-27 20:59:23

my 100th solved problem


Added by:Tomislav Babic
Date:2013-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2013 1. round