아리사는 에마에게 자신의 불 마법으로 제철 음식인 병 구이를 만들어주기로 했다.

아리사는 $N$가지의 불 마법을 사용할 수 있다. 단, 불 마법 숙련도가 부족한 관계로, 각 불 마법은 최대 한 번 씩만 사용할 수 있다. $i$번째 불 마법은 화력이 $F_i$이고, 이 마법으로 병을 구우면 에마는 $V_i$의 만족도를 얻는다.

에마는 $M$개의 병을 가져왔다. 이 병들은 일렬로 놓여 있고, $i$번째 병을 굽기 위해선 $A_i$ 이상의 화력이 필요하다.

아리사는 배고픈 에마를 위해 첫 번째 병($A_1$)부터 시작하여 중간에 건너뛰는 일 없이 연속으로 가능한 많은 병을 구워 주고자 하며, 그러한 방법이 여러 개라면 에마가 얻을 만족도의 총합을 최대화하고자 한다.

아리사를 위해, 구울 수 있는 최대 병의 개수와 그때의 최대 만족도 합을 알려주자!

제한

• $1 \le N, M \le 200,000$
• $1 \le i \le N$에 대해 $1 \le F_i, V_i \le 10^9$
• $1 \le i \le M$에 대해 $1 \le A_i \le 10^9$

부분문제

1. (10점) $1 \le i \le M-1$인 모든 $i$에 대해 $A_i \ge A_{i+1}$, $1 \le i, j \le N, i \ne j$인 모든 $i, j$에 대해 $F_i \ne F_j$이며, ($F_i < F_j \iff V_i < V_j$)

2. (20점) $1 \le i \le M-1$인 모든 $i$에 대해 $A_i \ge A_{i+1}$, $1 \le i, j \le N, i \ne j$인 모든 $i, j$에 대해 $F_i \ne F_j$이며, ($F_i < F_j \iff V_i > V_j$)

3. (30점) $1 \le i, j \le N, i \ne j$인 모든 $i, j$에 대해 $F_i \ne F_j$이며, ($F_i < F_j \iff V_i > V_j$)

4. (40점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 불 마법의 개수 $N$과 병의 개수 $M$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐서 각 불 마법의 화력 $F_i$와 만족도 $V_i$가 공백으로 구분되어 주어진다.

$N+2$째 줄에 각 병을 굽기 위해 필요한 화력 $A_1, A_2, \dots, A_M$이 공백으로 구분되어 주어진다.

출력 형식

아리사가 구울 수 있는 병의 개수의 최댓값과 그 때 에마가 얻을 수 있는 만족도의 총합의 최댓값을 공백으로 구분하여 출력한다.

예제

예제 1

입력

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

출력

3 16

첫 번째 병을 세 번째 불로, 두 번째 병을 첫 번째 불로, 세 번째 병을 두 번째 불로 구우면 세 병을 구워 16의 만족도를 얻을 수 있다. 이보다 병을 더 굽거나, 더 많은 만족도를 얻을 수 없다.

예제 2

입력

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

출력

2 19

위 예제는 부분문제 1의 입력 조건을 만족한다.

예제 3

입력

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

출력

8 36

위 예제는 부분문제 2,3의 입력 조건을 만족한다.

예제 4

입력

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

출력

0 0

어떤 병도 구울 수 없다.