C - Assignment of Delivery Workers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は配送センターの管理者です。配送センターには N 人の配達員がおり、配達員には 1 から N までの番号が付けられています。配達員 i の体力値は A_i です。

今日は M 件の配達依頼があり、配達依頼 j をこなすには体力値が B_j 以上の配達員が必要です。各配達依頼にはちょうど 1 人の配達員を割り当てなければなりません。また、1 人の配達員は最大 1 件の配達依頼にしか割り当てられません。

ここで、配達依頼 j に配達員 i を割り当てたとき、 A_i = B_j であればその割り当てはぴったりであるとします。ぴったりの割り当ては、配達員の体力を無駄なく活かせるため理想的です。

高橋君は、以下の 2 つの目標をこの優先順位で達成したいと考えています。

  1. 第一目標： M 件すべての配達依頼に、必要な体力値を満たす配達員を割り当てる（すなわち、配達依頼 j に割り当てる配達員 i は A_i \geq B_j を満たす）。もしすべての配達依頼に配達員を割り当てることが不可能な場合は -1 を出力してください。
  2. 第二目標： 第一目標を達成する割り当ての中で、ぴったりの割り当て（ A_i = B_j となるペア）の数を最大化する。

第一目標が達成可能な場合、ぴったりの割り当ての最大数を出力してください。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • 1 行目には、配達員の人数を表す N と配達依頼の件数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各配達員の体力値を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各配達依頼の必要体力値を表す B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。

出力

すべての配達依頼に配達員を割り当てることが不可能な場合は -1 を出力してください。可能な場合は、ぴったりの割り当ての最大数を 1 行で出力してください。

入力例 1

4 3
3 5 5 7
5 4 3

出力例 1

2

入力例 2

3 3
2 4 6
3 5 7

出力例 2

-1

入力例 3

10 7
1 3 3 4 6 6 8 10 10 12
3 5 6 6 9 10 11

出力例 3

4

入力例 4

20 15
2 5 5 7 8 10 10 12 15 15 18 20 21 25 30 30 35 40 45 50
1 5 6 10 10 14 15 19 20 22 30 31 35 44 50

出力例 4

8

入力例 5

1 1
1000000000
1000000000

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is the manager of a delivery center. The delivery center has N delivery workers, numbered from 1 to N. The stamina value of delivery worker i is A_i.

Today there are M delivery requests, and delivery request j requires a delivery worker with a stamina value of at least B_j. Exactly one delivery worker must be assigned to each delivery request. Also, each delivery worker can be assigned to at most one delivery request.

Here, when delivery worker i is assigned to delivery request j, if A_i = B_j, then the assignment is called a perfect match. A perfect match is ideal because it makes full use of the delivery worker's stamina without waste.

Takahashi wants to achieve the following two goals in this order of priority:

  1. Primary goal: Assign a delivery worker who meets the required stamina value to all M delivery requests (that is, delivery worker i assigned to delivery request j must satisfy A_i \geq B_j). If it is impossible to assign a delivery worker to every delivery request, output -1.
  2. Secondary goal: Among all assignments that achieve the primary goal, maximize the number of perfect matches (pairs where A_i = B_j).

If the primary goal is achievable, output the maximum number of perfect matches.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers.

Input

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains N, the number of delivery workers, and M, the number of delivery requests, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the stamina values of each delivery worker, separated by spaces.
  • The third line contains B_1, B_2, \ldots, B_M, the required stamina values of each delivery request, separated by spaces.

Output

If it is impossible to assign a delivery worker to every delivery request, output -1. If it is possible, output the maximum number of perfect matches in one line.

Sample Input 1

4 3
3 5 5 7
5 4 3

Sample Output 1

2

Sample Input 2

3 3
2 4 6
3 5 7

Sample Output 2

-1

Sample Input 3

10 7
1 3 3 4 6 6 8 10 10 12
3 5 6 6 9 10 11

Sample Output 3

4

Sample Input 4

20 15
2 5 5 7 8 10 10 12 15 15 18 20 21 25 30 30 35 40 45 50
1 5 6 10 10 14 15 19 20 22 30 31 35 44 50

Sample Output 4

8

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1