B - 本の貸し出し 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は学校の図書委員です。今日は N 人の生徒が図書室に本を借りに来ています。

図書室では M 種類の本を貸し出しています。各本 i（1 \leq i \leq M）には「面白さ」 S_i と「難易度」 R_i が設定されています。難易度とは、その本を読むために必要な読解力のレベルを表します。それぞれの種類の本は十分な冊数が用意されているため、同じ種類の本を複数の生徒に同時に貸し出すことができます。

各生徒 j（1 \leq j \leq N）には「読解力」 T_j が定められており、生徒 j は難易度が T_j 以下の本のみ読むことができます。

高橋君は、各生徒に対して、その生徒が読める本の中から面白さが最も高い本を 1 冊選んで貸し出します。面白さが最も高い本が複数ある場合は、そのうちどれを選んでも構いません。読める本が 1 冊もない生徒には本を貸し出しません。

すべての生徒に対してこのように本を貸し出したとき、貸し出された本の面白さの合計を求めてください。本を借りなかった生徒については 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
  • 1 行目には、生徒の人数を表す N と、本の種類数を表す M が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、各本の情報が与えられる。
  • 1 + i 行目では、本 i の面白さ S_i と難易度 R_i が、スペース区切りで与えられる。
  • M + 2 行目では、各生徒の読解力 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

すべての生徒に貸し出された本の面白さの合計を 1 行で出力してください。

入力例 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

Score : 333 pts

Problem Statement

Takahashi is a library committee member at his school. Today, N students have come to the library to borrow books.

The library lends out M types of books. Each book i (1 \leq i \leq M) has an "interestingness" S_i and a "difficulty" R_i. The difficulty represents the reading comprehension level required to read that book. There are sufficiently many copies of each type of book, so the same type of book can be lent to multiple students simultaneously.

Each student j (1 \leq j \leq N) has a "reading comprehension" T_j, and student j can only read books whose difficulty is at most T_j.

For each student, Takahashi selects and lends one book with the highest interestingness among the books that student can read. If there are multiple books with the highest interestingness, any of them may be chosen. Students who cannot read any books are not lent a book.

When books are lent to all students in this manner, find the total interestingness of the books that were lent out. For students who did not borrow a book, count their contribution as 0 in the total.

Constraints

  • 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
  • All input values are integers

Input

N M
S_1 R_1
S_2 R_2
\vdots
S_M R_M
T_1 T_2 \ldots T_N
  • The first line contains N, the number of students, and M, the number of types of books, separated by a space.
  • From the 2nd line to the (M + 1)-th line, the information for each book is given.
  • The (1 + i)-th line contains the interestingness S_i and difficulty R_i of book i, separated by a space.
  • The (M + 2)-th line contains the reading comprehension values T_1, T_2, \ldots, T_N of each student, separated by spaces.

Output

Print the total interestingness of the books lent to all students on a single line.

Sample Input 1

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

Sample Output 1

18

Sample Input 2

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

Sample Output 2

57

Sample Input 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

Sample Output 3

730