IOI 만두

IOI社는 $M$개의 서로 다른 맛 IOI 만두를 만들었고, $i$번째 만두 가격은 $P_i$원입니다 ($1 \le i \le M$).

JOI社는 $N$종류의 만두 상자를 만듭니다. $j$번째 상자 ($1 \le j \le N$)는 최대 $C_j$개까지 담을 수 있고 가격은 $E_j$원입니다. 상자 종류 중 0종류 이상 $N$종류 이하를 각각 1개씩 주문해 만두를 나눠 담아 세트로 팔려 합니다. 세트 가격은 들어 있는 만두 가격의 합입니다.

모든 세트가 팔린다고 할 때, IOI社가 얻을 수 있는 이익(판매한 만두 가격 합에서 주문한 상자 가격 합을 뺀 값)의 최댓값을 구하세요. 상자에 넣지 않은 만두는 이익 계산에 영향을 주지 않습니다.

• 1번째 줄: $M$, $N$.
• 다음 $M$줄: $P_i$.
• 다음 $N$줄: $C_j$, $E_j$.

최대 이익 (정수, 1줄).

• $1 \le M \le 10\,000$.
• $1 \le N \le 500$.
• $1 \le P_i \le 10\,000$.
• $1 \le C_j \le 10\,000$.
• $1 \le E_j \le 10\,000$.