Arisa decided to make roasted bottles, a seasonal delicacy, for Emma using her fire magic.

Arisa can use $N$ types of fire magic. However, due to lack of proficiency, she can use each fire magic at most once. The $i$-th fire magic has a firepower of $F_i$, and if she uses this magic to make a roasted bottle, Emma gains a satisfaction of $V_i$.

Emma brought $M$ bottles. These bottles are arranged in a row, and to roast $i$-th bottle, a firepower of at least $A_i$ is required.

To feed hungry Emma, Arisa wants to roast as many bottles as possible continuously starting from the first bottle($A_1$) without skipping any. If there are multiple ways to roast the maximum number of bottles, she wants to maximize the total satisfaction Emma will recieve.

Help Arisa to find the maximum number of bottles that can be roasted while maximizing the total satisfaction.

Constraints

• $1 \le N, M \le 200,000$
• $1 \le F_i, V_i \le 10^9$ for all $1 \le i \le N$
• $1 \le A_i \le 10^9$ for all $1 \le i \le M$

Subtasks

1. (10 points) $A_i \ge A_{i+1}$ for all $1 \le i \le M-1$. For all $1 \le i, j \le N$ with $i \ne j$, $F_i \ne F_j$ and ($F_i < F_j \iff V_i < V_j$).

2. (20 points) $A_i \ge A_{i+1}$ for all $1 \le i \le M-1$. For all $1 \le i, j \le N$ with $i \ne j$, $F_i \ne F_j$ and ($F_i < F_j \iff V_i > V_j$).

3. (30 points) For all $1 \le i, j \le N$ with $i \ne j$, $F_i \ne F_j$ and ($F_i < F_j \iff V_i > V_j$).

4. (40 points) No additional constraints.

Input format

The first line contains two integers $N$ and $M$ separated by a space, representing the number of fire magics and the number of bottles, respectively. ($1 \le N, M \le 200,000$)

Each of the next $N$ lines contains two integers $F_i$ and $V_i$ separated by a space, representing the firepower and the satisfaction of the $i$-th fire magic. ($1 \le F_i, V_i \le 10^9$)

The $(N+2)$-th line contains $M$ integers $A_1, A_2, \dots, A_M$ separated by spaces, representing the firepower required to roast each bottle. ($1 \le A_i \le 10^9$)

Output format

Output two integers separated by a space: the maximum number of bottles Arisa can roast, and the maximum total satisfaction Emma can gain in that case.

Examples

Example 1

Input

4 4
8 5
3 2
12 9
9 1
10 5 2 100

Output

3 16

By roasting the first bottle with the 3rd magic, the second bottle with the 1st magic, and the third bottle with the 2nd magic, Arisa can roast 3 bottles and gain 16 satisfaction. It is impossible to roast more bottles or get more satisfaction.

Example 2

Input

10 10
45 5
110 9
25 3
65 7
5 1
15 2
75 8
55 6
120 10
35 4
100 90 80 70 60 50 40 30 20 10

Output

2 19

The above example satisfies the conditions of Subtask 1.

Example 3

Input

9 9
35 7
105 1
55 5
5 9
75 3
25 8
95 2
45 6
65 4
90 80 70 60 50 40 30 20 10

Output

8 36

The above example satisfies the conditions of Subtasks 2 and 3.

Example 4

Input

4 3
2 5
1 10
3 2
4 8
15 12 10

Output

0 0

No bottles can be roasted.