Minimizing Maximum Ball Count and Purchase Cost

You are given n A-type boxes and m B-type boxes. Initially, the i-th A-type box contains a_i balls of color i (each A‐box only contains balls of one distinct color) and has unlimited capacity. There are also m B-type boxes available for purchase. The cost of buying the i-th B-type box is w_i and its capacity limit is b_i (i.e. it can hold at most b_i balls).

You can perform any number of operations. In each operation you choose one ball from some box and move it to another box. After all operations the following constraints must be met:

1. Every box must contain balls of a single color.
2. There exists a sequence p of n boxes (each p_i can be any box, either an A-type or a purchased B-type box) such that for every color i (with i ranging from 1 to n), all balls of color i appear only in the i-th A-type box or in box p_i.

Your task is to decide which B-type boxes to purchase (possibly none) and perform a series of moves so that the maximum number of balls in any box is minimized. On top of that, among all strategies achieving this minimum maximum count, you must also minimize the total purchase cost of the B-type boxes.

Note: Unless otherwise stated, the term "box" refers to both A-type and B-type boxes.

Observation: For each color i, originally, there are a_i balls in the i-th A-type box. In the final configuration, you are allowed to split the balls of color i between its A-type box and at most one other box (which, if used, must be a purchased B-type box) such that neither box exceeds the maximum count X (the value you want to minimize). Hence, if a_i > X then the extra a_i - X balls must be moved to a helper box, and feasibility requires a_i ≤ 2X for that color.

For each color i with a_i > X, define the number of balls that must be shifted as r_i = a_i - X. To accommodate these, you need to assign each such color a distinct B-type box with capacity at least r_i. Each B-type box j can only be used for one color, and if it is assigned for color i, the condition r_i ≤ b_j must hold. The final answer consists of the minimized maximum balls per box (i.e. the smallest feasible X) and the corresponding minimum total purchase cost.

inputFormat

The first line contains two integers n and m, where n is the number of A-type boxes and m is the number of available B-type boxes.

The second line contains n integers: a₁, a₂, ..., a_n where a_i denotes the number of balls in the i-th A-type box (all of which are of color i).

The next m lines each contain two integers w_i and b_i, representing the cost and capacity limit of the i-th B-type box respectively.

outputFormat

Output two integers separated by a space: the minimized maximum number of balls in any box and the minimum total cost of purchasing B-type boxes to achieve that configuration.

sample

3 2
3 7 5
4 3
5 2

7 9