Trips

Interview

Time limit1sMemory limit128 MB

Summary

Match group sizes to trip intervals so that each interval gets at most one group and the number of matched intervals is maximized.

Level: Medium7 of 10
Topics: Greedy, Sorting, Two pointers, Intervals
Solved: No attempts yet

Problem

During the upcoming holiday season, many people want to take an unforgettable trip, and everyone prefers to travel together with a group of friends. A travel agency offers several group trips. For each trip the group size is restricted: a minimum and a maximum number of people are given. Each group may choose at most one trip, and each trip may be assigned to at most one group. A group can be assigned to a trip only if the group's size lies within that trip's allowed range.

The agency wants to organize as many trips as possible. Given the group sizes and the size limits of every trip, determine the maximum number of trips that can be arranged.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 400000$ , $1 \le m \le 400000$ ): the number of groups and the number of trips. Groups are numbered from $1$ to $n$ , and trips are numbered from $1$ to $m$ .

Each of the next $n$ lines contains one integer $s_i$ ( $1 \le s_i \le 10^9$ ), the size of the $i$ -th group.

Each of the following $m$ lines contains two integers $l_j$ and $u_j$ ( $1 \le l_j \le u_j \le 10^9$ ), the minimum and the maximum group size that trip $j$ can accept.

Output

Output a single integer $k$ ( $k \ge 0$ ): the maximum number of trips that can be arranged.

Examples3

Example 1
Input
```
5 4
54
6
9
42
15
6 6
20 50
2 8
7 20
```
Expected output
```
3
```
Example 2
Input
```
2 2
1
2
5 10
6 8
```
Expected output
```
0
```
Example 3
Input
```
3 3
1
2
3
1 1
2 2
3 3
```
Expected output
```
3
```