题目背景

规定 $\text{popcount}(x)$ 表示 $x$ 在二进制表示下所含 $1$ 的个数。

题目描述

您有一个二进制数 $B$（以一个长为 $n$ 的 $01$ 字符串形式给出）和长为 $m$ 的序列 $a$。

同时，您还需要对 $B$ 进行 $m$ 次操作。

其中，第 $i$ 个操作为 $B \gets B + 2^{a_i}$，其价值 $v_i$ 为 $B$ 在操作前后变化的位置数量，即 $v_i = \operatorname{popcount}(B \mathbin{\mathrm{xor}} (B + 2^{a_i}))$。

您需要解决两个问题：

• 您可以任意安排操作顺序，问在执行所有操作后，$\displaystyle \sum_{i=1}^mv_i$ 最大为多少？

• 您可以任意安排操作顺序，问在执行所有操作后，$\displaystyle \max_{i=1}^mv_i$ 最大为多少？

输入格式

第一行两个整数 $n,m$。

第二行一个长为 $n$ 的 $01$ 字符串，表示二进制数 $B$，从低位到高位依次给出。

第三行 $m$ 个整数 $a_1,a_2,\dots,a_m$。

输出格式

第一行一个整数，表示第一问的答案。

第二行一个整数，表示第二问的答案。

本题使用 Special Judge，若您的第一问答案正确，可以获得该测试点 $30\%$ 的分数，若您的第二问答案正确，可以获得该测试点另外 $70\%$ 的分数。

若您只回答了两问中的一问，请在另一个位置输出一个非负整数。

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

提示

【样例解释 #1】

对于第一问，依次执行第 $1,2,6,5,4,3$ 个操作可得到 $\displaystyle \sum\limits_{i=1}^mv_i=14$。

对于第二问，依次执行第 $6,5,4,3,1,2$ 个操作可得到 $\displaystyle \max\limits_{i=1}^mv_i=6$。

详细过程

【数据范围】

本题采用捆绑测试。

• Subtask 1（20 points）：$n,m\leq 10$。
• Subtask 2（30 points）：$n,m\leq 1000$。
• Subtask 3（20 points）：$B$ 中全为 $0$，且 $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）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$0\leq a_i< n$。