P7853 "EZEC-9" Carry

Let $\text{popcount}(x)$ denote the number of $1$ bits in the binary representation of $x$.

You are given a binary number $B$ (provided as a $01$ string of length $n$) and a sequence $a$ of length $m$. You also need to perform $m$ operations on $B$. In the $i$-th operation, $B \gets B + 2^{a_i}$. Its value $v_i$ is the number of bit positions that change in $B$ before and after the operation, i.e., $v_i = \operatorname{popcount}(B \mathbin{\mathrm{xor}} (B + 2^{a_i}))$. You need to solve two problems: - You may arrange the order of operations **arbitrarily**. After performing **all** operations, what is the maximum possible value of $\displaystyle \sum_{i=1}^m v_i$? - You may arrange the order of operations **arbitrarily**. After performing **all** operations, what is the maximum possible value of $\displaystyle \max_{i=1}^m v_i$?

The first line contains two integers $n, m$. The second line contains a $01$ string of length $n$, representing the binary number $B$, **given from the least significant bit to the most significant bit**. The third line contains $m$ integers $a_1, a_2, \dots, a_m$.

The first line contains one integer, the answer to the first question. The second line contains one integer, the answer to the second question. **This problem uses Special Judge. If your answer to the first question is correct, you can get $30\%$ of the score for that test point. If your answer to the second question is correct, you can get another $70\%$ of the score for that test point.** **If you answer only one of the two questions, please output a non-negative integer in the other position.**

**[Sample Explanation #1]** For the first question, performing operations $1, 2, 6, 5, 4, 3$ in order can achieve $\displaystyle \sum\limits_{i=1}^m v_i = 14$. For the second question, performing operations $6, 5, 4, 3, 1, 2$ in order can achieve $\displaystyle \max\limits_{i=1}^m v_i = 6$. [Detailed process](https://www.luogu.com.cn/paste/ycx4xov7) **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (20 points): $n, m \leq 10$. - Subtask 2 (30 points): $n, m \leq 1000$. - Subtask 3 (20 points): $B$ is all $0$, and $a_1 = 0$, $\forall i>1, a_{i-1} \leq a_i \leq a_{i-1} + 1$. - Subtask 4 (20 points): $n, m \leq 10^5$. - Subtask 5 (10 points): no special restrictions. For $100\%$ of the testdata, $1 \leq n, m \leq 10^6$, $0 \leq a_i < n$. Translated by ChatGPT 5