E - Print Factory Schedule Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は印刷工場の工場長です。工場では様々なサイズのポスターを印刷しています。

高橋君のもとに N 件の注文が届きました。i 番目の注文（1 \leq i \leq N）では、横幅 W_i、縦幅 H_i の同一サイズのポスターを C_i 枚印刷する必要があります。

工場には M 台の印刷機があります。j 番目の印刷機（1 \leq j \leq M）は、横幅が L_j 以上 R_j 以下であるポスターのみを印刷することができます。ポスターの縦幅による制限はありません。すなわち、H_i の値にかかわらず、L_j \leq W_i \leq R_j を満たしていれば、j 番目の印刷機で i 番目の注文のポスターを印刷できます。（なお、H_i は注文の情報として入力に含まれますが、印刷機の割り当てには影響しません。）

各印刷機は 1 日あたり高々 1 枚のポスターしか印刷できません。すなわち、ある 1 日において、1 台の印刷機に割り当てられるポスターは最大 1 枚であり、同じ日に同じ印刷機で複数の注文のポスターを印刷することはできません。

1 つの注文の C_i 枚のポスターを、複数の印刷機に分担させて印刷することが可能です。同じ日に複数の印刷機で同じ注文のポスターを並行して印刷しても構いませんし、異なる日にまたがって印刷しても構いません。また、ある印刷機が日によって異なる注文のポスターを印刷することも可能です。

すべての注文を完了するために必要な最小の日数を求めてください。ここで、すべての注文が完了するとは、各注文 i（1 \leq i \leq N）について、C_i 枚のポスターがすべて印刷し終わることを意味します。

ある注文 i について、L_j \leq W_i \leq R_j を満たす印刷機 j が 1 台も存在しない場合、その注文を印刷する手段がないため、すべての注文を完了することは不可能です。その場合は -1 を出力してください。

制約

  • 1 \leq N
  • 1 \leq M
  • N + M \leq 10^5
  • 1 \leq W_i \leq 10^9
  • 1 \leq H_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • \displaystyle \sum_{i=1}^{N} C_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • 入力はすべて整数である

入力

N M
W_1 H_1 C_1
W_2 H_2 C_2
\vdots
W_N H_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、注文の数を表す整数 N と、印刷機の台数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各注文の情報が与えられる。
  • 1 + i 行目では、i 番目の注文のポスターの横幅 W_i、縦幅 H_i、枚数 C_i がスペース区切りで与えられる。
  • N + 2 行目から N + M + 1 行目では、各印刷機の情報が与えられる。
  • N + 1 + j 行目では、j 番目の印刷機が印刷できるポスターの横幅の下限 L_j と上限 R_j がスペース区切りで与えられる。

出力

すべての注文を完了するために必要な最小の日数を 1 行で出力せよ。すべての注文を完了できない場合は -1 を出力せよ。

入力例 1

2 2
10 5 3
20 8 2
1 15
10 30

出力例 1

3

入力例 2

2 3
10 100 4
50 200 3
1 20
21 30
60 80

出力例 2

-1

入力例 3

5 6
5 10 10
12 20 8
20 30 15
30 40 7
40 50 12
1 10
1 25
10 35
15 45
25 50
35 45

出力例 3

9

入力例 4

12 15
3 100 5
8 200 12
15 150 20
22 300 18
27 120 25
35 80 14
42 90 30
50 110 22
60 130 16
75 160 28
90 170 10
100 180 24
1 20
1 30
5 25
10 40
20 50
25 60
30 70
40 80
45 100
55 95
70 110
80 120
1 100
35 45
90 100

出力例 4

15

入力例 5

1 1
1000000000 1000000000 1000000000
1 1000000000

出力例 5

1000000000

Score : 466 pts

Problem Statement

Takahashi is the manager of a printing factory. The factory prints posters of various sizes.

Takahashi has received N orders. The i-th order (1 \leq i \leq N) requires printing C_i posters of the same size, with a width of W_i and a height of H_i.

The factory has M printing machines. The j-th printing machine (1 \leq j \leq M) can only print posters whose width is at least L_j and at most R_j. There is no restriction regarding the height of the poster. That is, regardless of the value of H_i, the j-th printing machine can print posters for the i-th order as long as L_j \leq W_i \leq R_j holds. (Note that although H_i is included in the input as part of the order information, it does not affect the assignment of printing machines.)

Each printing machine can print at most one poster per day. That is, on any single day, at most one poster can be assigned to each printing machine, and a machine cannot print posters for multiple orders on the same day.

It is possible to distribute the C_i posters of a single order among multiple printing machines. Multiple printing machines can print posters for the same order in parallel on the same day, or the printing can span across multiple days. Also, a single printing machine can print posters for different orders on different days.

Find the minimum number of days required to complete all orders. Here, completing all orders means that for each order i (1 \leq i \leq N), all C_i posters have been printed.

If there is an order i for which no printing machine j satisfies L_j \leq W_i \leq R_j, there is no way to print that order, making it impossible to complete all orders. In this case, output -1.

Constraints

  • 1 \leq N
  • 1 \leq M
  • N + M \leq 10^5
  • 1 \leq W_i \leq 10^9
  • 1 \leq H_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • \displaystyle \sum_{i=1}^{N} C_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • All input values are integers.

Input

N M
W_1 H_1 C_1
W_2 H_2 C_2
\vdots
W_N H_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the integer N, representing the number of orders, and the integer M, representing the number of printing machines, separated by a space.
  • The next N lines (from the 2nd line to the N + 1-th line) provide the information for each order.
  • The 1 + i-th line contains the width W_i, height H_i, and the quantity C_i of the posters for the i-th order, separated by spaces.
  • The subsequent M lines (from the N + 2-th line to the N + M + 1-th line) provide the information for each printing machine.
  • The N + 1 + j-th line contains the lower bound L_j and upper bound R_j of the poster width that the j-th printing machine can print, separated by a space.

Output

Print the minimum number of days required to complete all orders in a single line. If it is impossible to complete all orders, print -1.

Sample Input 1

2 2
10 5 3
20 8 2
1 15
10 30

Sample Output 1

3

Sample Input 2

2 3
10 100 4
50 200 3
1 20
21 30
60 80

Sample Output 2

-1

Sample Input 3

5 6
5 10 10
12 20 8
20 30 15
30 40 7
40 50 12
1 10
1 25
10 35
15 45
25 50
35 45

Sample Output 3

9

Sample Input 4

12 15
3 100 5
8 200 12
15 150 20
22 300 18
27 120 25
35 80 14
42 90 30
50 110 22
60 130 16
75 160 28
90 170 10
100 180 24
1 20
1 30
5 25
10 40
20 50
25 60
30 70
40 80
45 100
55 95
70 110
80 120
1 100
35 45
90 100

Sample Output 4

15

Sample Input 5

1 1
1000000000 1000000000 1000000000
1 1000000000

Sample Output 5

1000000000