Horse Carts

시간 제한1초메모리 제한2048 MB

요약

마차 M대가 각각 무게 한도까지 보물 하나씩 운반할 때, 가져갈 수 있는 보물 가치 합의 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

You just found a cave filled with $N$ treasures (numbered from $1$ to $N$ ). Treasure $i$ has a weight of $W\_i$ and a value of $V\_i$ .

Luckily, you also bring $M$ horse carts (numbered from $1$ to $M$ ) to help you carry the treasures. Each cart can only carry one treasure; cart $j$ can only carry a treasure with weight at most $S\_j$ .

Determine the maximum total value of treasures that you can take using your horse carts.

입력

The first line consists of two integers $N$ $M$ ( $1 ≤ N, M ≤ 100\\, 000$ ).

Each of the next $N$ lines consists of two integers $W\_i$ $V\_i$ ( $1 ≤ W\_i , V\_i ≤ 10^6$ ).

The following line consists of $M$ integers $S\_j$ ( $1 ≤ S\_j ≤ 10^6$ ).

출력

Output a single integer representing the maximum total value of treasures that you can take using your horse carts.

예제4

예제 1

입력

예상 출력

예제 2
입력
```
5 3
1 4
1 2
1 7
1 1
1 9
1 1 1
```
예상 출력
```
20
```
예제 3
입력
```
2 5
9 100
4 100
1 2 3 1 3
```
예상 출력
```
0
```

예제 4

입력

예상 출력