생선 장수

면접 대비

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

요약
각 fishmonger가 원하는 마릿수와 킬로그램당 가격이 주어질 때, 물고기를 배분해 얻을 수 있는 최대 수익을 구한다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 힙, 배열
정답자
아직 제출이 없습니다

문제

당신은 물고기를 잡는다.

당신은 물고기를 싫어한다.

당신은 돈을 사랑한다.

그러므로 물고기를 판다.

생선 장수들에게.

최대 이익을 위해.

입력

첫째 줄에 당신이 팔아야 하는 물고기의 수 nn (1≤n≤100 0001 \le n \le 100\,000)과 생선 장수의 수 mm (1≤m≤100 0001 \le m \le 100\,000)이 주어진다. 둘째 줄에는 nn개의 정수 w1,w2,…,wnw_1, w_2, \ldots, w_n이 공백으로 구분되어 주어지며, 이는 각 물고기의 무게(킬로그램)이다 (1≤wi≤100 0001 \le w_i \le 100\,000). 마지막으로 mm개의 줄이 주어지며, jj번째 줄은 두 정수 xjx_j (1≤xj≤100 0001 \le x_j \le 100\,000)와 pjp_j (1≤pj≤100 0001 \le p_j \le 100\,000)로 이루어진다. 이는 각각 jj번째 생선 장수가 사려는 물고기의 수와 킬로그램당 지불할 금액이다.

출력

생선 장수들에게 물고기를 팔아 얻을 수 있는 최대 금액을 정수로 출력한다.

예제1

  1. 예제 1

    입력
    4 3
1 2 7 5
2 4
1 5
3 3
    예상 출력
    66