D - プリンターの割り当て 解説 /

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

配点 : 400 点

問題文

高橋君は大学の印刷センターで管理者として働いています。この印刷センターには N 台のプリンターがあり、それぞれ 1 から N までの番号が付けられています。

各プリンター i には、1回の印刷で処理できる最大ページ数 W_i と、1件の依頼を処理するのにかかる時間 T_i が定められています。依頼のページ数によらず、プリンター i で1件の依頼を処理する時間は常に T_i です。

今日、印刷センターには M 件の印刷依頼が届きました。各依頼 j には、印刷すべきページ数 P_j が指定されています。

1つの依頼は分割できず、そのページ数以上の最大ページ数を持つプリンター1台で処理しなければなりません。すなわち、依頼 j をプリンター i で処理するには W_i \geq P_j である必要があります。

各プリンターは同時に1つの依頼しか処理できません。プリンターは依頼の処理が終わると、すぐに次の依頼を処理できます。すべてのプリンターは時刻 0 から稼働可能です。各依頼はどの時刻に処理を開始しても構いませんが、すべての依頼を処理しなければなりません。

高橋君は、すべての依頼を処理し終える最も早い時刻、すなわち最後の依頼の処理が完了する時刻を最小化したいと考えています。

すべての M 件の依頼を処理できる場合は、すべての依頼が完了する最も早い時刻を出力してください。処理できない依頼が存在する場合、すなわちどのプリンターでも処理できないページ数の依頼がある場合は -1 を出力してください。

制約

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

入力

N M
W_1 T_1
W_2 T_2
:
W_N T_N
P_1
P_2
:
P_M
  • 1 行目には、プリンターの台数を表す N と、印刷依頼の件数を表す M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各プリンターの情報が与えられる。
  • 1 + i 行目には、プリンター i の最大ページ数 W_i と印刷時間 T_i がスペース区切りで与えられる。
  • N + 2 行目から N + M + 1 行目では、各依頼のページ数が与えられる。
  • N + 1 + j 行目には、依頼 j のページ数 P_j が与えられる。

出力

すべての依頼を処理できる場合は、すべての依頼が完了する最も早い時刻を 1 行で出力せよ。処理できない依頼が存在する場合は -1 を 1 行で出力せよ。

入力例 1

2 3
10 5
20 7
8
15
10

出力例 1

10

入力例 2

2 3
5 3
10 2
4
11
8

出力例 2

-1

入力例 3

5 10
30 8
10 3
50 15
20 6
40 10
5
12
18
25
35
45
9
20
30
40

出力例 3

20

入力例 4

10 25
100 12
50 5
200 30
80 9
150 18
60 7
120 14
40 4
180 25
90 10
35
42
58
61
79
83
99
101
119
121
145
149
151
175
180
190
200
50
50
75
110
130
160
20
100

出力例 4

90

入力例 5

1 1
1000000000 1000000000
1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi works as an administrator at a university printing center. In this printing center, there are N printers, numbered 1 to N.

Each printer i has a maximum page capacity W_i that it can process in a single print job, and a processing time T_i required to process one job. Regardless of the number of pages in a job, the time required for printer i to process a single job is always T_i.

Today, M print jobs have arrived at the printing center. Each job j has a specified number of pages P_j to be printed.

A single job cannot be split and must be processed by a single printer whose maximum page capacity is at least the number of pages in the job. That is, to process job j with printer i, we must have W_i \geq P_j.

Each printer can process at most one job at a time. As soon as a printer finishes processing a job, it can immediately start processing the next one. All printers are available starting from time 0. Each job can start processing at any time, but all jobs must be processed.

Takahashi wants to minimize the earliest time by which all jobs are processed, i.e., the completion time of the last job.

If it is possible to process all M jobs, output the earliest time by which all jobs can be completed. If there is any job that cannot be processed (i.e., there is a job with a number of pages that no printer can handle), output -1.

Constraints

  • 1 \leq N, M
  • N + M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.

Input

N M
W_1 T_1
W_2 T_2
:
W_N T_N
P_1
P_2
:
P_M
  • The first line contains N, the number of printers, and M, the number of print jobs, separated by a space.
  • The next N lines, from the 2nd line to the (N + 1)-th line, provide the information of each printer.
  • The (1 + i)-th line contains W_i, the maximum page capacity of printer i, and T_i, its processing time, separated by a space.
  • The next M lines, from the (N + 2)-th line to the (N + M + 1)-th line, provide the number of pages for each job.
  • The (N + 1 + j)-th line contains P_j, the number of pages for job j.

Output

If it is possible to process all jobs, output the earliest time by which all jobs can be completed in a single line. If there is a job that cannot be processed, output -1 in a single line.

Sample Input 1

2 3
10 5
20 7
8
15
10

Sample Output 1

10

Sample Input 2

2 3
5 3
10 2
4
11
8

Sample Output 2

-1

Sample Input 3

5 10
30 8
10 3
50 15
20 6
40 10
5
12
18
25
35
45
9
20
30
40

Sample Output 3

20

Sample Input 4

10 25
100 12
50 5
200 30
80 9
150 18
60 7
120 14
40 4
180 25
90 10
35
42
58
61
79
83
99
101
119
121
145
149
151
175
180
190
200
50
50
75
110
130
160
20
100

Sample Output 4

90

Sample Input 5

1 1
1000000000 1000000000
1000000000

Sample Output 5

1000000000