점검일이 낀 납기 주문 정산

문제

한 공장의 생산 라인은 하루에 주문 한 건만 완성할 수 있다. 날짜는 1일부터 차례로 번호가 붙고, 주문 하나를 완성하는 데에는 정확히 하루가 걸리며 한 주문을 여러 날에 나누어 만들 수는 없다. 이 라인에는 정기 점검이 잡힌 날이 M개 있고, 점검일에는 라인이 멈추므로 어떤 주문도 완성할 수 없다. 점검일 목록에는 같은 날짜가 두 번 나오지 않는다. 접수된 주문은 N건이다. i번째 주문에는 납기일 d_i와 정산금 p_i가 정해져 있다. 주문은 납기일 당일을 포함해 그 날짜까지 완성되어야 정산금 p_i를 받고, 납기까지 완성하지 못하거나 아예 만들지 않은 주문의 정산금은 0이다. 납기일이 점검일과 겹치는 주문도 있을 수 있으며, 그런 주문은 납기일 이전의 가동일에 완성해야 한다. 같은 날짜에 두 건 이상을 만들 수 없고, 납기가 지난 날짜에 만든 주문은 정산받을 수 없다. 정산금이 같은 주문이 여러 건이어도 각각 별개의 주문으로 취급한다. 어떤 주문을 만들고 어떤 가동일에 배정할지는 마음대로 정할 수 있으며, 만들지 않고 비워 두는 가동일이 있어도 된다. 정산금의 총합이 최대가 되도록 주문을 골랐을 때, 그 최댓값을 구하시오.

입력

첫 줄에 정수 N, M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ M ≤ 200,000) 둘째 줄에 점검일 M개가 공백으로 구분되어 주어진다. 모두 서로 다르며 1 이상 10^9 이하의 정수이다. 이어지는 N개의 줄에 각각 납기일 d_i와 정산금 p_i가 공백으로 구분되어 주어진다. (1 ≤ d_i ≤ 10^9, 1 ≤ p_i ≤ 10^9)

출력

정산금 총합의 최댓값을 한 줄에 출력한다.

4 1
2
2 10
2 7
3 5
3 8

18

3 2
1 2
1 5
2 9
4 3

3

출처: Devin.KR 자체 제작