만두 팔기 Batch Compilation commands

상수는 만두를 만들어 생계를 유지하고 있습니다. 오늘 그는 $M$종류의 만두를 각각 한 개씩 만들었습니다. 이 만두들은 크기가 모두 같지만 맛이 다르기 때문에 가격이 가지각색입니다. $i$ ($1 \le i \le M$) 번 만두의 가격은 $P_{i}$원입니다.

승현이는 상자들을 만들어 생계를 유지하고 있습니다. 그는 $N$종류의 포장 상자들을 판매하고 있으며, 이 중 $j$ ($1 \le j \le N$)번 상자에는 최대 $C_{j}$개의 만두를 넣을 수 있고 그 가격은 $E_{j}$원입니다.

상수는 승현이에게 한 종류당 최대 한 개의 상자를 구매하여 만두들을 이 상자에 나누어 넣어서 판매하고 한 상자를 한 세트라고 정의하기로 합니다. 각 만두 세트의 가격은 그 안에 들어있는 만두들의 가격의 합입니다. 상수는 모든 만두 세트들이 팔린다고 가정할 때 자신이 얻을 수 있는 최대 이익을 알고자 합니다. 이 때 이익은 판매한 만두 세트들의 가격의 합에서 승현이에게 구매한 상자들의 가격의 합을 뺀 값입니다. 상자에 넣지 않은 만두는 상수가 먹으면 되므로 이익에 영향을 주지 않습니다.

해야 할 일

상수가 만든 각 만두의 가격과 승현이가 판매하는 각 상자의 크기와 가격이 주어질 때, 상수가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하세요.

입력

• 첫 번째 줄에 상수가 만든 만두의 종류의 수 $M$과 승현이가 판매하는 상자의 종류의 수 $N$이 공백을 사이로 두고 주어집니다.
• $M$개 줄이 주어집니다. 이 중 $i$ ($1 \le i \le M$)번째 줄에는 $i$번 만두의 가격 $P_{i}$가 주어집니다.
• $N$개 줄이 주어집니다. 이 중 $j$ ($1 \le j \le N$)번째 줄에는 $i$번 상자에 넣을 수 있는 최대 만두의 수 $C_{j}$와 그 가격 $E_{j}$가 주어집니다.

출력 형식

첫 번째 줄에 상수가 얻을 수 있는 최대 이익을 출력합니다.

제약 조건

• $1 \le M \le 10,000$
• $1 \le N \le 500$
• $1 \le P_{i} \le 10,000$ ($1 \le i \le M$)
• $1 \le C_{j} \le 10,000$ ($1 \le j \le N$)
• $1 \le E_{j} \le 10,000$ ($1 \le j \le N$)
• 모든 $P_{i}$, $C_{j}$, $E_{j}$는 정수입니다.

서브태스크

서브태스크 1 [25점]

$N \le 10$

서브태스크 2 [25점]

$C_{j} \le 10$ ($1 \le j \le N$)

서브태스크 3 [40점]

추가적인 제약 조건이 없습니다.

예제

입력

4 3
180
160
170
190
2 100
3 120
4 250

출력

480

상수는 승현이로부터 1번 상자 ($100$원)와 2번 상자 ($120$원)를 구매합니다. 상수는 1번 상자에 1번 만두와 2번 만두를 담아 $180 + 160 = 340$원에, 2번 상자에 3번 만두와 4번 만두를 담아 $170 + 190 = 360$원에 판매합니다. 이렇게 하면 이익은 $700 - 220 = 480$원입니다.

입력

2 2
1000
2000
1 6666
1 7777

출력

0

상자가 더 비싸니까 그냥 아무것도 안 하는 것이 최선입니다.

입력

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

출력

450