题目描述

育华学校为了迎接劳动节，准备举办一场校园装饰活动。学校有 $n$ 个大型储物箱（A 类箱子），这些储物箱用于存放不同颜色的装饰球，第 $i$ 个大型储物箱里有 $a_i$ 个颜色为 $i$ 的装饰球，并且每个大型储物箱的容量没有限制。

此外，学校还可以从供应商那里购买 $m$ 种小型收纳盒（C 类箱子），购买第 $i$ 个小型收纳盒的花费为 $w_i$，且它有大小上限 $C_i$。

为了让装饰球的存放更加规整，工作人员可以进行任意次操作，每次选择一个箱子里的一个装饰球，把它放到另一个箱子中，但要保证最终：

• 每个箱子中的装饰球颜色相同。

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

工作人员需要购买若干个小型收纳盒后（可以不购买）进行上述操作，使得所有箱子中装饰球的数量的最大值最小，并且在此基础上最小化购买小型收纳盒的总花费。

若未特别标注，则「箱子」表示「大型储物箱」与「小型收纳盒」的总称。

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3 3

输入输出样例 #2

输入 #2

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

输出 #2

4 7

输入输出样例 #3

输入 #3

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

输出 #3

3 10

输入输出样例 #4

输入 #4

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

输出 #4

3 3

说明/提示

【样例解释 #1】

育华学校的工作人员买第 $1$ 个小型收纳盒 $(3,3)$，并将第 $1$ 个大型储物箱中的 $2$ 个颜色为 $1$ 的装饰球放到这个小型收纳盒中即可，花费为 $3$。

【样例解释 #2】

工作人员买第 $1$ 个小型收纳盒 $(5,2)$ 和第 $4$ 个小型收纳盒 $(1,5)$，并将第 $1$ 个大型储物箱中的 $1$ 个颜色为 $1$ 的装饰球放到第 $4$ 个小型收纳盒，将第 $3$ 个大型储物箱中的 $3$ 个颜色为 $3$ 的装饰球放到第 $1$ 个大型储物箱，将第 $5$ 个大型储物箱中的 $3$ 个颜色为 $5$ 的装饰球放到第 $1$ 个小型收纳盒，所有箱子中装饰球数量最大值为 $4$，花费为 $7$。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1 \le n,m \le 2 \times 10^5$，$1\le a_i,C_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,C_i \le 2$	$15$
$5$			无	$40$