今年も，全国プログラミング選手権大会の時期がやってきた．全国大会の参加権を賭けた地区大会は， 2ⁿ チームが1 対1 の勝ち残り式トーナメント方式で対決する．

トーナメント表にはチーム番号 0, . . . 2ⁿ − 1 が割り振られており，1 回戦から n 回戦までの対決手順は次の通りである．

1. 1 回戦では，（チーム番号が l のチーム）と（チーム番号が l + 1 のチーム）が対決する．(l ≡ 0 (mod 2))
2. i + 1 回戦(1 ≤ i < n) では，「チーム番号が l 以上 l + 2ⁱ 未満のチームのうち， i 回戦までの対決で 1 回も負けていないチーム」と「チーム番号が l + 2ⁱ 以上 l + 2ⁱ⁺¹ 未満のチームのうち， i 回戦までの対決で一回も負けていないチーム」が対決する．(l ≡ 0 (mod 2ⁱ⁺¹))

n 回戦まで終わると，各チームの順位は 2^{n − (そのチームが勝った回数)} 位で確定する．なお，この対決には引き分けが存在しないため，対決したチームのいずれか一方が勝ち，もう一方が負ける．

晴れて地区大会の代表に選ばれた私達は，他の地区大会の結果をマネージャーに調べてもらうことにした．ここで調べてもらった結果が「マネージャーから受け取った順位表」であった．「マネージャーから受け取った順位表」をより詳細に説明すると，長さ 2ⁿ の数列で i ( 0 ≤ i ≤ 2ⁿ − 1 ) 番目の要素にチーム番号 i のチームの順位が書かれているものである．

だが，「マネージャーから受け取った順位表」には同じ順位が大量に並んでいた！トーナメントのルール上，同じ順位が大量に並ぶなんてありえないはずだ．そこで，「マネージャーから受け取った順位表」を「無矛盾な順位表」にするために順位を変更するチーム数の最小値を計算してどのくらい順位表が間違っているかをマネージャーに教えてあげよう．「無矛盾な順位表」とは，順位が確定したトーナメントの結果として起こりうる順位表のことを表す．

Input

入力には，「マネージャーから受け取った順位表」が以下の形式で与えられる．

n m
a0 a1 . . .  am
b0 b1 . . .  bm−1

• 1 行目は n, m の2 個の整数からなり， 2ⁿ は「地区大会の参加チーム数」，m は「『マネージャーから受け取った順位表』で連続した順位が並んでいる区間の個数」を表す．
• 2 行目は a_i(0 ≤ i ≤ m) の m + 1 個の整数からなり，各 a_i は「『マネージャーから受け取った順位表』で連続した順位が並んでいる区間の区切り位置」を表す．
• 3 行目は b_i(0 ≤ i < m) の m 個の整数からなり，各2^b_i は「『マネージャーから受け取った順位表』におけるチーム番号が a_i 以上 a_i+1 未満のチームの順位」を表す．

Constraints

• 1 ≤ n ≤ 30
• 1 ≤ m ≤ 10,000
• 0 = a₀ < a₁ ≤ . . . ≤ a_m−1 < a_m = 2ⁿ
• 0 ≤ b_i ≤ n

Output

「マネージャーから受け取った順位表」を「無矛盾な順位表」にするために順位を変更するチーム数の最小値を1 行に出力せよ．

Sample Input 1

1 1
0 2
1

Output for the Sample Input 1

1

参加チーム数が2 の「無矛盾な順位表」は，{"チーム番号 0 のチームの順位", "チーム番号 1 のチームの順位"} として {1, 2} と {2, 1} の2 通りがある．順位表 {2, 2} を「無矛盾な順位表」に修正するためには，いずれかのチームの順位を 1 に変更しなければならない．

Sample Input 2

2 3
0 1 2 4
0 1 2

Output for the Sample Input 2

2

Sample Input 3

2 3
0 1 3 4
0 2 1

Output for the Sample Input 3

0

Sample Input 4

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

Output for the Sample Input 4

10