codeforces#P1310B. Double Elimination

Double Elimination

Description

The biggest event of the year – Cota 2 world championship "The Innernational" is right around the corner. 2n2^n teams will compete in a double-elimination format (please, carefully read problem statement even if you know what is it) to identify the champion.

Teams are numbered from 11 to 2n2^n and will play games one-on-one. All teams start in the upper bracket.

All upper bracket matches will be held played between teams that haven't lost any games yet. Teams are split into games by team numbers. Game winner advances in the next round of upper bracket, losers drop into the lower bracket.

Lower bracket starts with 2n12^{n-1} teams that lost the first upper bracket game. Each lower bracket round consists of two games. In the first game of a round 2k2^k teams play a game with each other (teams are split into games by team numbers). 2k12^{k-1} loosing teams are eliminated from the championship, 2k12^{k-1} winning teams are playing 2k12^{k-1} teams that got eliminated in this round of upper bracket (again, teams are split into games by team numbers). As a result of each round both upper and lower bracket have 2k12^{k-1} teams remaining. See example notes for better understanding.

Single remaining team of upper bracket plays with single remaining team of lower bracket in grand-finals to identify championship winner.

You are a fan of teams with numbers a1,a2,...,aka_1, a_2, ..., a_k. You want the championship to have as many games with your favourite teams as possible. Luckily, you can affect results of every championship game the way you want. What's maximal possible number of championship games that include teams you're fan of?

First input line has two integers n,kn, k — 2n2^n teams are competing in the championship. You are a fan of kk teams (2n17;0k2n2 \le n \le 17; 0 \le k \le 2^n).

Second input line has kk distinct integers a1,,aka_1, \ldots, a_k — numbers of teams you're a fan of (1ai2n1 \le a_i \le 2^n).

Output single integer — maximal possible number of championship games that include teams you're fan of.

Input

First input line has two integers n,kn, k — 2n2^n teams are competing in the championship. You are a fan of kk teams (2n17;0k2n2 \le n \le 17; 0 \le k \le 2^n).

Second input line has kk distinct integers a1,,aka_1, \ldots, a_k — numbers of teams you're a fan of (1ai2n1 \le a_i \le 2^n).

Output

Output single integer — maximal possible number of championship games that include teams you're fan of.

Samples

输入数据 1

3 1
6

输出数据 1

6

输入数据 2

3 3
1 7 8

输出数据 2

11

输入数据 3

3 4
1 3 5 7

输出数据 3

14

Note

On the image, each game of the championship is denoted with an English letter (aa to nn). Winner of game ii is denoted as WiWi, loser is denoted as LiLi. Teams you're a fan of are highlighted with red background.

In the first example, team 66 will play in 6 games if it looses the first upper bracket game (game cc) and wins all lower bracket games (games h,j,l,mh, j, l, m).

In the second example, teams 77 and 88 have to play with each other in the first game of upper bracket (game dd). Team 88 can win all remaining games in upper bracket, when teams 11 and 77 will compete in the lower bracket.

In the third example, your favourite teams can play in all games of the championship.