D - Part-Time Job Shift Assignment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はアルバイト先の店長として、シフト管理を担当しています。

今後 N 日間の営業についてシフトを組む必要があります。各営業日には 1, 2, \ldots, N と番号が付けられており、営業日 i (1 \leq i \leq N) には、必要スキルレベル H_i と売上見込み S_i が設定されています。

高橋君の店には M 人のアルバイトが在籍しており、各アルバイト j (1 \leq j \leq M) にはスキルレベル P_j が決まっています。アルバイト j を営業日 i に割り当てるには、H_i \leq P_j を満たす必要があります。つまり、その日の必要スキルレベル以上のスキルを持つアルバイトのみ割り当てることができます。

高橋君は M 人のアルバイト全員をそれぞれ異なる営業日に割り当てたいと考えています。M \leq N であるため、アルバイトが割り当てられない営業日が存在することもあります。具体的には、割り当ては以下の条件をすべて満たす必要があります。

  • 各アルバイトはちょうど 1 つの営業日に割り当てられる。すなわち、M 人全員がいずれかの営業日に割り当てられ、割り当てられない人はいない。
  • 各営業日に割り当てられるアルバイトは高々 1 人である。すなわち、同じ営業日に 2 人以上のアルバイトが割り当てられることはない。
  • アルバイト j が営業日 i に割り当てられるならば、H_i \leq P_j でなければならない。

アルバイトが割り当てられた営業日についてのみ、その売上見込みが得られるものとします。すなわち、ある割り当て方においてアルバイトが割り当てられた営業日の集合を T としたとき、その割り当て方における 売上の合計 は \displaystyle\sum_{i \in T} S_i です。

上記の条件を満たすようにすべてのアルバイトを割り当てることが可能かどうかを判定してください。可能な場合は、条件を満たすすべての割り当て方の中での売上の合計の最大値を求めてください。不可能な場合は -1 を出力してください。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 1 \leq P_j \leq 10^9
  • 入力はすべて整数
  • H_i, S_i, P_j の値は、同じ種類の変数間でも異なる種類の変数間でも重複することがある

入力

N M
H_1 S_1
H_2 S_2
\vdots
H_N S_N
P_1 P_2 \ldots P_M
  • 1 行目には、営業日数を表す整数 N と、アルバイトの人数を表す整数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、営業日 i の必要スキルレベル H_i と売上見込み S_i がスペース区切りで与えられる。
  • 最後の行には、各アルバイトのスキルレベル P_1, P_2, \ldots, P_M がスペース区切りで与えられる。

出力

すべてのアルバイトを条件を満たすようにそれぞれ異なる営業日に割り当てることが可能な場合は、売上の合計の最大値を 1 行で出力せよ。不可能な場合は -1 を出力せよ。

入力例 1

5 3
3 100
5 200
2 150
4 80
1 50
4 3 2

出力例 1

330

入力例 2

4 3
5 100
5 200
5 300
5 400
3 4 2

出力例 2

-1

入力例 3

8 5
10 500
7 300
15 800
5 200
12 600
3 100
8 450
20 1000
8 12 5 15 10

出力例 3

2550

Score : 400 pts

Problem Statement

Takahashi is in charge of shift management as the store manager at his part-time workplace.

He needs to create a shift schedule for the upcoming N business days. Each business day is numbered 1, 2, \ldots, N, and business day i (1 \leq i \leq N) has a required skill level H_i and an expected sales amount S_i.

Takahashi's store has M part-time workers, and each worker j (1 \leq j \leq M) has a skill level P_j. To assign worker j to business day i, the condition H_i \leq P_j must be satisfied. In other words, only workers whose skill level is at least the required skill level for that day can be assigned to it.

Takahashi wants to assign all M part-time workers to distinct business days. Since M \leq N, there may be business days with no worker assigned. Specifically, the assignment must satisfy all of the following conditions:

  • Each worker is assigned to exactly 1 business day. That is, all M workers are assigned to some business day, and no one is left unassigned.
  • At most 1 worker is assigned to each business day. That is, no business day has 2 or more workers assigned to it.
  • If worker j is assigned to business day i, then H_i \leq P_j must hold.

The expected sales are obtained only for business days that have a worker assigned. That is, if the set of business days with assigned workers in a certain assignment is T, then the total sales for that assignment is \displaystyle\sum_{i \in T} S_i.

Determine whether it is possible to assign all workers in a way that satisfies the above conditions. If it is possible, find the maximum total sales among all valid assignments. If it is impossible, output -1.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 1 \leq P_j \leq 10^9
  • All inputs are integers
  • The values of H_i, S_i, P_j may coincide, both among variables of the same type and among variables of different types

Input

N M
H_1 S_1
H_2 S_2
\vdots
H_N S_N
P_1 P_2 \ldots P_M
  • The first line contains an integer N representing the number of business days and an integer M representing the number of part-time workers, separated by a space.
  • The following N lines, where line i (1 \leq i \leq N), contain the required skill level H_i and expected sales S_i for business day i, separated by a space.
  • The last line contains the skill levels P_1, P_2, \ldots, P_M of each part-time worker, separated by spaces.

Output

If it is possible to assign all workers to distinct business days satisfying the conditions, output the maximum total sales in one line. If it is impossible, output -1.

Sample Input 1

5 3
3 100
5 200
2 150
4 80
1 50
4 3 2

Sample Output 1

330

Sample Input 2

4 3
5 100
5 200
5 300
5 400
3 4 2

Sample Output 2

-1

Sample Input 3

8 5
10 500
7 300
15 800
5 200
12 600
3 100
8 450
20 1000
8 12 5 15 10

Sample Output 3

2550