← 返回题目列表

AtCoder · awc0099_b

B. 图书借阅

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥是他所在学校的图书馆委员会成员。今天, N 同学们纷纷来图书馆借书。

图书馆借出 M 书籍类型。每本书 i (1 \leq i \leq M)具有“趣味性” S_i 和一个“困难” R_i。难度代表阅读该书所需的阅读理解水平。每种类型的书都有足够多的册数,因此同一类型的书可以同时借给多个学生。

每位学生 j (1 \leq j \leq N) 有“阅读理解能力” T_j和学生 j 只能阅读难度最高为 T_j.

高桥为每个学生选择并借出一本学生可以阅读的书中趣味性最高的书。如果有多本有趣度最高的书,则可以选择其中任何一本。不会读书的学生不会借书。

当以这种方式向所有学生借书时,找出所借书的总兴趣度。对于没有借书的学生,将他们的贡献算作 总计 0 。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • 1 \leq T_j \leq 10^9
  • 所有输入值均为整数

输入

N M
S_1 R_1
S_2 R_2
\vdots
S_M R_M
T_1 T_2 \ldots T_N
  • 第一行包含 N,学生人数,以及 M,图书类型数量,以空格分隔。
  • 从第 2 行到 (M + 1)第行,给出每本书的信息。
  • 的 (1 + i)- 第行包含有趣的内容 S_i 和难度 本书的 R_i 书的 i,用空格分隔。
  • 的 (M + 2)第行包含阅读理解值 每个学生的 T_1, T_2, \ldots, T_N ,用空格分隔。

输出

在一行中打印出借给所有学生的书籍的总兴趣。


示例输入 1

3 4
5 3
8 5
3 1
10 7
4 7 2

示例输出 1

18

示例输入 2

6 5
10 5
7 3
15 10
4 2
20 8
1 3 5 8 10 1

示例输出 2

57

示例输入 3

10 8
100 50
30 10
80 40
50 20
200 100
60 30
90 60
10 5
5 15 25 35 45 55 70 100 3 50

示例输出 3

730