Description

Initially, you have $n$ A-type boxes, where the $i$-th A-type box contains $a_i$ balls of color $i$. Each A-type box has unlimited capacity. Additionally, there are $m$ B-type boxes available for purchase. The $i$-th B-type box costs $w_i$ and has a maximum capacity of $b_i$.

You can perform any number of operations, where each operation involves moving one ball from one box to another. However, the final state must satisfy:

1. Every box contains balls of a single color.
2. There exists a sequence $p$ of length $n$ (where $p_i$ can represent either an A-type or B-type box) such that for all $i \in [1, n]$, balls of color $i$ only appear in the $i$-th A-type box or the box $p_i$.

Your task is to purchase some B-type boxes (possibly none) and perform the operations to minimize the maximum number of balls in any box across all boxes. Under this condition, you must also minimize the total cost of purchased B-type boxes.

Unless explicitly specified, the term "box" refers to both A-type and B-type boxes collectively.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$.

The next $m$ lines each contain two positive integers $b_i$ and $w_i$.

Output Format

Output two integers: the minimum possible maximum number of balls in any box, and the minimum total cost under this condition.

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

Hint

Explanation #1

Purchase the first B-type box $(3, 3)$. Move 2 color-1 balls from the first A-type box to this B-type box. The maximum number of balls in any box is $3$, and the total cost is $3$.

Explanation #2

Purchase the first B-type box $(5, 2)$ and the fourth B-type box $(1, 5)$. Move 1 color-1 ball from the first A-type box to the fourth B-type box, 3 color-3 balls from the third A-type box to the first B-type box, and 3 color-5 balls from the fifth A-type box to the first B-type box. The maximum number of balls is $4$, and the total cost is $7$.

Constraints

This problem uses subtask scoring.

For all test data: $1 \le n, m \le 2 \times 10^5$, $1 \le a_i, b_i, w_i \le 10^9$.

Translated by DeepSeek R1