题目背景

原题链接：https://oier.team/problems/X11D。

---

「少しの眠れぬ夜に」

「この魔法がほのかに灯るなら」

「今がそんなに悪くないって」

「笑える時まで今日もscience!」

题目描述

初始你有 $n$ 个 A 类盒子，第 $i$ 个盒子里有 $a_i$ 个颜色为 $i$ 的球，且每个 A 类盒子的大小无限制。还有 $m$ 个 B 类盒子，购买第 $i$ 个 B 类盒子的花费为 $w_i$，且有大小上限 $b_i$。

你可以进行任意次操作，每次选择一个盒子里的一个球，把它放到另一个盒子中，但你要保证最终：

• 每个盒子中的球颜色相同。

• 存在序列长度为 $n$ 的盒子序列 $p$（即盒子 $p_i$ 可以表示任意一个 A 类或 B 类盒子），满足对于所有 $i\in[1,n]$，颜色为 $i$ 的小球只会出现在第 $i$ 个 A 类盒子或盒子 $p_i$。

你要购买若干个 B 类盒子后（可以不购买）进行上述操作使得所有盒子中球的数量的最大值最小，并且在此基础上最小化购买 B 类盒子的总花费。

若未特别标注，则「盒子」表示「A 类盒子」与「B 类盒子」的总称。

输入格式

第一行，两个整数 $n,m$。

接下来一行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

最后 $m$ 行，每行两个正整数 $b_i,w_i$。

输出格式

一行两个整数，分别表示所有盒子中球个数最大值的最小值和在此前提下的最小花费。

5 3
5 2 1 3 2 
3 3
1 5
1 4

3 3

5 5
1 1 7 4 7 
5 2
5 7
1 6
1 5
2 10

4 7

5 3
1 2 5 4 4 
3 5
4 4
2 1

3 10

5 3
2 4 3 3 4 
1 1
4 4
5 2

3 3

提示

【样例解释 #1】

买第 $1$ 个 B 类盒子 $(3,3)$，并将第 $1$ 个 A 类盒子中的 $2$ 个颜色为 $1$ 的球放到这个 B 类盒子中即可，花费为 $3$。

【样例解释 #2】

买第 $1$ 个 B 类盒子 $(5,2)$ 和第 $4$ 个 B 类盒子 $(1,5)$，并将第 $1$ 个 A 类盒子中的 $1$ 个颜色为 $1$ 的球放到第 $4$ 个 B 类盒子，将第 $3$ 个 A 类盒子中的 $3$ 个颜色为 $3$ 的球放到第 $1$ 个 A 类盒子，将第 $5$ 个 A 类盒子中的 $3$ 个颜色为 $5$ 的球放到第 $1$ 个 B 类盒子，所有盒子球数最大值为 $4$，花费为 $7$。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1 \le n,m \le 2 \times 10^5$，$1\le a_i,b_i,w_i \le 10^9$。

子任务编号	$n\le$	$m \le$	特殊性质	分值
$1$	$6$		无	$10$
$2$	$2 \times 10^5$	$1$		$15$
$3$		$5$		$20$
$4$		$2 \times 10^5$	保证所有 $a_i,b_i \le 2$	$15$
$5$			无	$40$