Background

Define $\text{popcount}(x)$ as the number of $1$s in the binary representation of $x$.

Problem Description

You are given a binary number $B$ (represented as a string of length $n$ consisting of $0$s and $1$s) and a sequence $a$ of length $m$.

You need to perform $m$ operations on $B$.

In the $i$-th operation, $B$ is updated to $B + 2^{a_i}$, and the value $v_i$ is the number of positions that change 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 can arrange the operations in any order. What is the maximum possible value of $\displaystyle \sum_{i=1}^mv_i$ after performing all operations?

• You can arrange the operations in any order. What is the maximum possible value of $\displaystyle \max_{i=1}^mv_i$ after performing all operations?

Input Format

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

The second line contains a 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 should contain an integer representing the answer to the first question.

The second line should contain an integer representing the answer to the second question.

This problem uses a Special Judge. If your answer to the first question is correct, you can get $30\%$ of the points for that test case. If your answer to the second question is correct, you can get the remaining $70\%$ of the points for that test case.

If you only answer one of the questions, please output a non-negative integer in the other position.

Sample Input and Output

Sample Input #1

5 6
10110
1 0 2 2 2 2

Sample Output #1

14
6

Sample Input #2

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

Sample Output #2

21
9

Sample Input #3

10 3
1111101111
5 5 0

Sample Output #3

13
11

Notes

[Sample Explanation #1]

For the first question, performing the operations in the order of $1, 2, 6, 5, 4, 3$ yields $\displaystyle \sum_{i=1}^mv_i = 14$.

For the second question, performing the operations in the order of $6, 5, 4, 3, 1, 2$ yields $\displaystyle \max_{i=1}^mv_i = 6$.

Detailed Process

[Data Range]

This problem uses bundled testing.

• Subtask 1 (20 points): $n, m \leq 10$.
• Subtask 2 (30 points): $n, m \leq 1000$.
• Subtask 3 (20 points): $B$ consists entirely of $0$s, 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 data, $1 \leq n, m \leq 10^6$, $0 \leq a_i < n$.

见题面 Input 部分

见题面 Output 部分