MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\\\(","\\\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

### 题目描述

又到了全国编程选手锦标赛的季节。为了参加全国大赛，地区赛以 1 对 1 的淘汰赛方式进行，共有 $2^n$ 支队伍参赛。

每个队伍都被分配了一个编号从 $0$ 到 $2^n-1$ 的队伍号码，第一轮到第 $n$ 轮比赛的对阵顺序如下：

1. 第一轮中，编号为 $l$ 的队伍和编号为 $l+1$ 的队伍对阵（$l \equiv 0 \pmod{2}$）。
2. 第 $i+1$ 轮（$1 \leq i < n$）中，编号为 $l$ 到 $l+2^i-1$ 的队伍中，“第 $i$ 轮前比赛从未输过的队伍”和编号为 $l+2^i$ 到 $l+2^{i+1}-1$ 的队伍中，“第 $i$ 轮前比赛从未输过的队伍”进行对阵（$l \equiv 0 \pmod{2^{i+1}}$）。

比赛进行到第 $n$ 轮结束后，每个队伍的名次是确定的，并且按照 $2^{n-\text{队伍的胜利次数}}$ 来确定名次。需要注意的是，由于比赛不允许平局，对阵的两支队伍必定有一方获胜，另一方失败。

我们幸运地被选为地区赛的代表，并决定让经理帮我们调查其他地区赛的结果。经理给我们提供了一个“来自经理的名次表”。具体来说，这个名次表是一个长度为 $2^n$ 的序列，其中第 $i$（$0 \leq i \leq 2^n-1$）个元素表示队伍号码为 $i$ 的队伍的名次。

然而，“来自经理的名次表”中存在大量相同的名次！根据比赛规则，名次不应该出现大量相同的情况。因此，为了将“来自经理的名次表”变为“无矛盾的名次表”，我们需要计算改变名次的最小队伍数量，并告诉经理名次表错误的程度。

“无矛盾的名次表”是指排位确定的比赛结果可能生成的名次表。

* * *

### 输入

输入的格式如下：

> $n$ $m$  
> $a_0$ $a_1$ ... $a_m$  
> $b_0$ $b_1$ ... $b_{m-1}$

*   第一行包含两个整数 $n$ 和 $m$，其中 $2^n$ 表示“地区大赛的参赛队伍数”，$m$ 表示“连续出现相同名次的区间数量”。
*   第二行包含 $m+1$ 个整数 $a_i$（$0 \le i \le m$），表示“来自经理的名次表”中连续出现相同名次的区间的分割位置。
*   第三行包含 $m$ 个整数 $b_i$（$0 \le i < m$），其中 $2^{b_i}$ 表示“来自经理的名次表”中队伍号码在 $a_i$ 到 $a_{i+1}-1$ 范围内的名次。

#### 约束条件

*   $1 \le n \le 30$
*   $1 \le m \le 10,000$
*   $0=a_0 < a_1 < \cdots < a_{m-1} < a_m = 2^n$
*   $0 \le b_i \le n$

### 输出

输出一个整数，表示将“来自经理的名次表”变为“无矛盾的名次表”所需改变名次的最小队伍数量。

* * *

### 示例 1

```plain
1 1
0 2
1```

### 对应的输出示例 1

```plain
1```

参赛队伍数为 2 时，可能的“无矛盾的名次表”有两种情况：{队伍号码为 0 的队伍的名次, 队伍号码为 1 的队伍的名次} 为 $\\{1,2\\}$ 和 $\\{2,1\\}$。要将名次表 $\\{2,2\\}$ 变为“无矛盾的名次表”，需要将某个队伍的名次修改为 1。

* * *

### 示例 2

```plain
2 3
0 1 2 4
0 1 2```

### 对应的输出示例 2

```plain
2```

* * *

### 示例 3

```plain
2 3
0 1 3 4
0 2 1```

### 对应的输出示例 3

```plain
0```

* * *

### 示例 4

```plain
4 5
0 1 2 4 8 16
0 1 2 3 4```

### 对应的输出示例 4

```plain
10```

* * *