问题陈述
今年,国家项目NGU球员权利锦标赛的时机终于到来。 地区锦标赛中,你可以投注全国锦标赛的参赛资格,双方将以$2^n$的队伍进行一对一淘汰赛制对决。
锦标赛积分榜的队伍编号为$0,\ldots,2^n-1$,从第一轮到$n$轮的对决顺序如下。
- 第一轮,队号$l和队号$l+1$的队伍对决。 $l \equiv 0 ~(\bmod~2)$)
- 在$i+1$轮($1 \le i < n$)中,队号在$l$至$l+2^i$之间且至第$i轮未输过一场比赛的队伍,$l指的是队伍号码在+2^i$至$l+2^{i+1}$之间且至第$i轮未输过任何比赛的队伍。 ($l \equiv 0~(\bmod~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}$
- 第1行包含两个整数 $n,m$,其中 $2^n$ 表示“地区大会的参赛队伍数”,$m$ 表示“在‘从经理那里收到的排名表’中连续排名并列的区间数量”。
- 第2行包含 $a_i(0 \le i \le m)$ 共 $m+1$ 个整数,每个 $a_i$ 表示“在‘从经理那里收到的排名表’中连续排名并列的区间的分界位置”。
- 第3行包含 $b_i(0 \le i < m)$ 共 $m$ 个整数,每个 $2^{b_i}$ 表示“在‘从经理那里收到的排名表’中,队号在 $a_i$ 及以上且小于 $a_{i+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行,表示为了将“从经理那里收到的排名表”变为“无矛盾的排名表”所需修改排名的最少队伍数。
示例输入 1
1 1 0 2 1
样本输入 1 的输出
1
两支参赛队伍的“稳定排名”为{”チーム番号0のチームの順位","チーム番号1のチームの順位使用“}有两种方式:$\{1,2\}$和$\{2,1\}$。 要将排名$\{2,2\}$修改为“稳定排名”,必须将一队排名改为1。
示例输入 2
2 3 0 1 2 4 0 1 2
样本输入 2 的输出
2
示例输入 3
2 3 0 1 3 4 0 2 1
样本输入 3 的输出
0
示例输入 4
4 5 0 1 2 4 8 16 0 1 2 3 4
样本输入 4 的输出
10