P12149 【MX-X11-T3】Science

原题链接：。 --- 「少しの眠れぬ夜に」 「この魔法がほのかに灯るなら」 「今がそんなに悪くないって」 「笑える時まで今日もscience!」

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.**

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 two integers: the minimum possible maximum number of balls in any box, and the minimum total cost under this condition.

## 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$. | Subtask | $n \le$ | $m \le$ | Special Property | Points | |:---------:|:---------------:|:---------------:|:----------------------------------------:|:--------:| | 1 | 6 | 6 | None | 10 | | 2 | $2 \times 10^5$ | 1 | None | 15 | | 3 | $2 \times 10^5$ | 5 | None | 20 | | 4 | $2 \times 10^5$ | $2 \times 10^5$ | All $a_i, b_i \le 2$ | 15 | | 5 | $2 \times 10^5$ | $2 \times 10^5$ | None | 40 | Translated by DeepSeek R1