题目描述

在“智慧校园”项目中，决定为学校的每个教室安装一台新一代空调，用于自动制冷和通风。根据设计，每个教室只能装一台空调，且空调的功率必须满足教室的大小——教室越大，空调功率越强。

学校的教室编号从 $1$ 到 $n$ 连续排列。已知编号为 $i$ 的教室需要一台功率至少为 $a_i$ 瓦特的空调。

学校管理层提供了 $m$ 种不同型号的空调可供采购。每种型号的空调都有对应的功率和价格。请你写个程序，算出给所有教室配备空调所需的最低总花费。

输入格式

第一行包含一个整数 $n\ (1 \le n \le 50\,000)$，表示教室数量。

第二行包含 $n$ 个整数 $a_i\ (1 \le a_i \le 1000)$，表示编号为 $i$ 的教室所需空调的最低功率（瓦特）。

第三行包含一个整数 $m\ (1 \le m\le 50\,000)$，表示可选空调型号数量。

接下来 $m$ 行，每行包含两个整数 $b_j$ 和 $c_j\ (1 \le b_j \le 1000, 1 \le c_j \le 1000)$，分别表示第 $j$ 种空调的功率（瓦特）和价格。

输出格式

输出一个整数，表示给所有教室配备空调的最低总花费。保证至少存在一种方案能满足所有教室的需求。

1
800
1
800 1000

1000

3
1 2 3
4
1 10
1 5
10 7
2 3

13

提示

第一个样例中，只能买唯一一台空调，价格是 $1000$ 元。

第二个样例中，最优方案是给第 $1$ 和第 $2$ 个教室装第 $4$ 种型号的空调，给第 $3$ 个教室装第 $3$ 种型号的空调，总价是 $13$ 元（$3 + 3 + 7$）。

评分

对于 $50$ 分的数据，$n,m\le1000$。

翻译来源：GPT 4.1 mini。