Description

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$?

Input Format

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

Output Format

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.

5 6
10110
1 0 2 2 2 2

14
6

10 10
0101010110
0 1 2 3 4 5 5 4 3 2

21
9

10 3
1111101111
5 5 0

13
11

Hint

[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

[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