#1970. 小偷

小偷

题目背景

有一些物品和一个小偷。

题目描述

NN 件物品,每件物品有质量 MiM_i 和价值 ViV_i

面条老师 有 KK 个袋子,每袋可容纳的最大质量为 CiC_i

每袋仅能放一个物品,问最多可以带走多少价值的物品?

输入格式

第一行包含两个正整数 NNKK

接下来 NN 行中的每行包含两个正整数 MiM_iViV_i

接下来 KK 行中的每行包含一个正整数 CiC_i

输出格式

输出一行,能拿走的最大物品总价值。

样例 #1

样例输入 #1

2 1
5 10
100 100
11

样例输出 #1

10

样例 #2

样例输入 #2

3 2
1 65
5 23
2 99
10
2

样例输出 #2

164

提示

【数据规模与约定】

  • 1N,K3×1051\le N,K\le 3\times 10^5
  • 1Mi,Vi1061\le M_i,V_i\le 10^6
  • 1Ci1081\le C_i\le 10^8

样例 2 解释

将第一件物品放在第二袋中,将第三件物品放在第一袋中。