에어컨

«스마트 스쿨» 사업에서는 대상 학교의 모든 교실에 자동 냉방과 환기를 위한 차세대 에어컨을 한 대씩 설치하기로 했다. 교실마다 에어컨은 정확히 한 대만 설치해야 하고, 그 출력은 교실 크기에 충분해야 한다. 교실이 클수록 더 강한 에어컨이 필요하다.

학교의 모든 교실에는 1부터 n까지 차례로 번호가 붙어 있다. 번호 i인 교실에는 출력이 $a_i$ 와트 이상인 에어컨이 정확히 한 대 필요하다.

학교 측은 구매할 수 있는 서로 다른 m가지 에어컨 모델 목록을 받았다. 각 모델의 출력과 가격을 알고 있다. 학교의 모든 교실에 에어컨을 설치하는 데 드는 총비용의 최솟값을 구하는 프로그램을 작성하라.

입력 파일의 첫째 줄에는 정수 n (1 ≤ n ≤ 50,000)이 주어진다. 이는 학교의 교실 수이다.

둘째 줄에는 n개의 정수 $a_i$ (1 ≤ $a_i$ ≤ 1000)가 주어진다. 이는 번호 i인 교실에 설치할 수 있는 에어컨의 최소 출력(와트)이다.

셋째 줄에는 정수 m (1 ≤ m ≤ 50,000)이 주어진다. 이는 제안된 에어컨 모델의 수이다.

다음 m개 줄에는 각각 정수 쌍 $b_j$ 와 $c_j$ (1 ≤ $b_j$ ≤ 1000, 1 ≤ $c_j$ ≤ 1000)가 주어진다. 이는 j번째 에어컨 모델의 출력(와트)과 가격(루블)이다.

출력 파일에는 에어컨 총비용의 최솟값을 루블 단위로 하나 출력한다. 올바른 에어컨 선택이 적어도 하나 존재하고, 모든 교실에 알맞은 에어컨을 설치할 수 있음이 보장된다.

첫 번째 예에서는 구매할 수 있는 유일한 에어컨을 1000루블에 사야 한다.

두 번째 예에서는 첫 번째와 두 번째 교실에 네 번째 모델의 에어컨을, 세 번째 교실에 세 번째 모델의 에어컨을 설치하는 것이 최적이다. 이 에어컨들의 총비용은 13루블 (3 + 3 + 7)이다.