408206: GYM103053 E Scythes and Monsters

There are $$$n$$$ monsters in the Underworld. Monster $$$i$$$ has attributes $$$a_i$$$ and $$$b_i$$$. Calliope has $$$m$$$ one-time use scythes, where scythe $$$i$$$ has power $$$d_i$$$. Calliope can kill monster $$$i$$$ with scythe $$$j$$$ if $$$d_j \geq a_i$$$ OR $$$d_j \leq b_i$$$. Each scythe can only be used to kill one monster.

Find the maximum number of monsters that Calliope can kill.

The first line consists of two space-separated integers, $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 10^6)$$$.

The second line consists of $$$n$$$ space-separated integers, $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.

The third line consists of $$$n$$$ space-separated integers, $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 10^9)$$$.

The fourth line consists of $$$m$$$ space-separated integers, $$$d_1, d_2, \ldots, d_m$$$ $$$(1 \leq d_i \leq 10^9)$$$.

Output a single integer, the maximum number of monsters that Calliope can kill.

Subtask 1 (8 points): $$$b_i=1,\,d_i \geq 2$$$ for all $$$i$$$

Subtask 2 (7 points): $$$1 \leq n,m \leq 11$$$

Subtask 3 (8 points): $$$1 \leq n,m \leq 100$$$

Subtask 4 (7 points): $$$1 \leq n,m \leq 500$$$

Subtask 5 (12 points): $$$1 \leq n,m \leq 3000$$$

Subtask 6 (43 points): $$$1 \leq n,m \leq 10^5$$$

Subtask 7 (15 points): No additional constraints

5 4
10 10 6 6 6
3 4 1 2 1
6 5 7 6

3

6 5
3 7 9 4 6 8
1 2 2 3 4 2
3 2 5 3 4

4

3 4
8 9 10
1 2 3
4 5 6 7

0

For convenience, define a-kill and b-kill as killing with $$$d_j\geq a_i$$$ and $$$d_j \leq b_i$$$ respectively.

Sample 1: The monster $$$(a,b)$$$-pairs are $$$(10,3),(10,3),(6,1),(6,2),(6,1)$$$. One way to kill $$$3$$$ monsters is to use scythes $$$1,3,4$$$ (with values $$$6,7,6$$$) to a-kill monsters $$$3,4,5$$$ respectively. Scythe $$$2$$$ cannot kill any monster, so the answer is $$$3$$$.

Sample 2: One way to achieve the answer: Scythes $$$1,3$$$ a-kill monsters $$$1,4$$$ respectively; scythes $$$2,4$$$ b-kill monsters $$$2,5$$$ respectively.

Sample 3: None of the scythes can kill any monster, so the answer is $$$0$$$.