/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は、学校の遠足で N 台のバスを手配しました。バス i の車内の天井の高さ（床から天井までの高さ）は D_i です。N 台のバスの天井の高さはすべて異なります。
遠足には M 人の生徒が参加します。生徒 j はクラス名 S_j で表されるクラスに所属しており、身長は H_j です。クラス名が同じ生徒は同じクラスに所属しています。
高橋君は、M 人の生徒全員をいずれかのバスに割り当てます。このとき、以下の条件を満たさなければなりません。
- すべての生徒はちょうど 1 台のバスに割り当てられる。
- 同じクラスに所属する生徒は、全員同じバスに割り当てなければならない。
なお、1 台のバスに割り当てる人数に上限はありません。また、誰も割り当てられないバスがあっても構いません。
生徒 j がバス i に割り当てられたとき、身長が天井の高さより大きい、すなわち H_j > D_i であるならば、その生徒は乗車中ずっと頭を下げていなければならず、不快な思いをします。身長が天井の高さ以下（H_j \leq D_i）であれば不快にはなりません。
上記の条件を満たす割り当て方のうち、不快な思いをする生徒の合計人数の最小値を求めてください。
制約
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^5
- 1 \leq D_i \leq 10^9 \quad (1 \leq i \leq N)
- D_i はすべて異なる。
- S_j は英小文字のみからなる長さ 1 以上 10 以下の文字列である。 (1 \leq j \leq M)
- 1 \leq H_j \leq 10^9 \quad (1 \leq j \leq M)
- N, M, D_i, H_j はすべて整数である。
入力
N M D_1 D_2 \ldots D_N S_1 H_1 S_2 H_2 \vdots S_M H_M
- 1 行目には、バスの台数 N と生徒の人数 M が、スペース区切りで与えられる。
- 2 行目には、各バスの天井の高さ D_1, D_2, \ldots, D_N がスペース区切りで与えられる。
- 続く M 行のうち j 行目（全体では 2 + j 行目）には、生徒 j の所属クラス名 S_j と身長 H_j がスペース区切りで与えられる。
出力
不快な思いをする生徒の合計人数の最小値を 1 行で出力せよ。
入力例 1
3 5 160 180 200 a 150 a 170 b 190 c 210 c 180
出力例 1
1
入力例 2
2 4 150 170 red 160 blue 180 red 140 green 130
出力例 2
1
入力例 3
10 24 145 190 170 230 155 210 180 200 165 220 alpha 160 beta 175 gamma 225 alpha 150 delta 205 beta 195 epsilon 140 gamma 235 zeta 180 eta 215 theta 155 iota 198 kappa 221 delta 199 epsilon 160 zeta 175 eta 225 theta 166 iota 188 kappa 219 lambda 230 lambda 120 mu 1000000000 mu 210
出力例 3
2
入力例 4
30 60 120 135 150 165 180 195 210 225 240 255 270 285 300 315 330 345 360 375 390 405 420 435 450 465 480 495 510 525 540 555 ant 118 bee 136 cat 151 dog 166 eel 181 fox 196 goat 211 hare 226 ibis 241 jay 256 kiwi 271 lion 286 mole 301 newt 316 otter 331 pig 346 quail 361 rat 376 seal 391 toad 406 ant 421 bee 436 cat 451 dog 466 eel 481 fox 496 goat 511 hare 526 ibis 541 jay 556 kiwi 130 lion 145 mole 160 newt 175 otter 190 pig 205 quail 220 rat 235 seal 250 toad 265 ant 280 bee 295 cat 310 dog 325 eel 340 fox 355 goat 370 hare 385 ibis 400 jay 415 kiwi 430 lion 445 mole 460 newt 475 otter 490 pig 505 quail 520 rat 535 seal 550 toad 565
出力例 4
2
入力例 5
1 1 1 abcdefghij 1000000000
出力例 5
1
Score : 233 pts
Problem Statement
Takahashi has arranged N buses for a school trip. The ceiling height (distance from the floor to the ceiling) of bus i is D_i. All N buses have pairwise distinct ceiling heights.
There are M students participating in the trip. Student j belongs to a class represented by the class name S_j, and their height is H_j. Students with the same class name belong to the same class.
Takahashi will assign all M students to one of the buses. In doing so, the following conditions must be satisfied:
- Every student is assigned to exactly 1 bus.
- All students belonging to the same class must be assigned to the same bus.
Note that there is no upper limit on the number of students assigned to a single bus. Also, there may be buses to which no students are assigned.
When student j is assigned to bus i, if their height is greater than the ceiling height, i.e., H_j > D_i, they must keep their head down during the ride, making them feel uncomfortable. If their height is less than or equal to the ceiling height (H_j \leq D_i), they will not feel uncomfortable.
Find the minimum possible total number of students who feel uncomfortable among all valid assignments.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^5
- 1 \leq D_i \leq 10^9 \quad (1 \leq i \leq N)
- All D_i are pairwise distinct.
- S_j is a string of length between 1 and 10, inclusive, consisting of lowercase English letters. (1 \leq j \leq M)
- 1 \leq H_j \leq 10^9 \quad (1 \leq j \leq M)
- N, M, D_i, and H_j are all integers.
Input
N M D_1 D_2 \ldots D_N S_1 H_1 S_2 H_2 \vdots S_M H_M
- The first line contains the number of buses N and the number of students M, separated by a space.
- The second line contains the ceiling heights of the buses D_1, D_2, \ldots, D_N, separated by spaces.
- The j-th of the following M lines (which is the (2 + j)-th line in total) contains the class name S_j and the height H_j of student j, separated by a space.
Output
Print the minimum possible total number of students who feel uncomfortable in a single line.
Sample Input 1
3 5 160 180 200 a 150 a 170 b 190 c 210 c 180
Sample Output 1
1
Sample Input 2
2 4 150 170 red 160 blue 180 red 140 green 130
Sample Output 2
1
Sample Input 3
10 24 145 190 170 230 155 210 180 200 165 220 alpha 160 beta 175 gamma 225 alpha 150 delta 205 beta 195 epsilon 140 gamma 235 zeta 180 eta 215 theta 155 iota 198 kappa 221 delta 199 epsilon 160 zeta 175 eta 225 theta 166 iota 188 kappa 219 lambda 230 lambda 120 mu 1000000000 mu 210
Sample Output 3
2
Sample Input 4
30 60 120 135 150 165 180 195 210 225 240 255 270 285 300 315 330 345 360 375 390 405 420 435 450 465 480 495 510 525 540 555 ant 118 bee 136 cat 151 dog 166 eel 181 fox 196 goat 211 hare 226 ibis 241 jay 256 kiwi 271 lion 286 mole 301 newt 316 otter 331 pig 346 quail 361 rat 376 seal 391 toad 406 ant 421 bee 436 cat 451 dog 466 eel 481 fox 496 goat 511 hare 526 ibis 541 jay 556 kiwi 130 lion 145 mole 160 newt 175 otter 190 pig 205 quail 220 rat 235 seal 250 toad 265 ant 280 bee 295 cat 310 dog 325 eel 340 fox 355 goat 370 hare 385 ibis 400 jay 415 kiwi 430 lion 445 mole 460 newt 475 otter 490 pig 505 quail 520 rat 535 seal 550 toad 565
Sample Output 4
2
Sample Input 5
1 1 1 abcdefghij 1000000000
Sample Output 5
1