题目描述

有一个无盖的长方形盒子。沿着盒子的长度方向，每隔 $1$ 厘米放置一块横向隔板。每块隔板有一个高度。

下足够多的雨之后，盒子中会蓄满它在当前隔板高度下所能容纳的最大水量。

现在有一些指定隔板可以被增高。对每个这样的隔板，给定它最多可以增加的高度，且增加量必须是整数。你需要回答：为了使盒子能够容纳的水量达到最大值，至少需要增高多少块隔板？同时输出这个最大水量。

请编写程序求出答案。

输入格式

第一行一个整数 $N$，表示隔板数量。

第二行包含 $N$ 个整数，按从左到右的顺序给出每块隔板的初始高度。

第三行一个整数 $K$，表示可以增高的隔板数量。

接下来 $K$ 行，每行两个整数：

p d

表示编号为 $p$ 的隔板最多可以增加 $d$ 厘米。

隔板编号从 $0$ 开始。

输出格式

输出一行两个整数，中间用一个空格隔开：

最少需要增高的隔板数 最大蓄水量

其中最大蓄水量以立方厘米为单位。

说明

由于盒子的宽度视为 $1$ 厘米，因此蓄水量可以直接按二维截面面积计算，单位为立方厘米。

盒子的前后壁视为足够高，高于任意隔板增高后的高度。盒子的左壁和右壁分别与最左侧、最右侧隔板重合，因此左右边界高度就是最左和最右隔板增高后的高度。

数据范围

• $1<N<1\,000\,000$；
• $0<K\le N$；
• 每块隔板的初始高度为正整数，且小于 $1\,000\,000$；
• 每个可增高隔板的最大增高量为正整数，且小于 $1\,000\,000$。

评分方式

每个测试点单独计分。

样例

输入

6
2 4 2 4 2 1
2
2 1
4 1

输出

1 14

解释

编号为 $2$ 的隔板不需要增高，因为增高它不会改变总蓄水量。

将编号为 $4$ 的隔板增高 $1$ 厘米，可以让最大蓄水量增加 $1$ 立方厘米。为了达到最大蓄水量，只需增高这一块隔板，因此答案为 1 14。