User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

48.3% (14/29)

Description

到魔法都市一段時間後,魔理沙的魔法能力有了大幅進展
此時魔理沙詠唱每個魔法句子 $K$ 時只要消耗 $K$ 點魔力 ( 過去為 $2K$ 點) ,但她還是想要更進一步

在深入學習魔法理論後她知道了魔法使們能夠從 $ᚠ$ 構造出所有魔法句子,故 $ᚠ$ 被稱為起源文字,由於起源文字能夠直接從自然界所包含的魔力生成,因此不需要花費魔法使本身的魔力

而關於詠唱魔法句子所需要的魔力有以下規則:

  • 文字 $ᚠ$ 是所有魔法的起點,需要的魔力為 $0$ 點
  • 每個魔法句子 $K$ 可透過增加 $1$ 詠唱魔力來變化為另外兩種新的魔法句子 $K + ᚢ$ 和 $K + ᚦ$
  • 已經詠唱過的魔法句子,不需重新花費魔力

例如要詠唱魔法文字 $ᚠᚢᚢ$ 和 $ᚠᚢᚦ$ , 由於他們都是從 $ᚠᚢ$ 變化而來,不需要重頭從 $ᚠ$ 開始詠唱,因此只需詠唱 ${ᚠ}+{ᚠᚢ} +{ᚠᚢᚢ}+{ᚠᚢᚦ}$,而魔力需求為 $0+1+1+1=3$ ,即已經詠唱完成的文字可以重複使用在魔法中

再例如詠唱 $ᚠᚢᚢ$ 和 $ᚠᚦᚦ$ 需要詠唱 ${ᚠ} +{ᚠᚢ} +{ᚠᚢᚢ}+{ᚠᚦ}+{ᚠᚦᚦ}$,花費魔力為 $0+1+1+1+1=4$

作為普通人類,直接記憶文字太麻煩,因此她對所有句子進行了編號,編號規則 $T$ 為:

  • $T(ᚠ) = 1$
  • 對於任意句子 $K + ᚢ$ 有 $T(K + ᚢ) = 2\times T(K) + 0$
  • 對於任意句子 $K + ᚦ$ 有 $T(K + ᚦ) = 2\times T(K) + 1$

例如 $T(ᚠᚢ) = 2, T(ᚠᚦ) = 3, T(ᚠᚢᚢ) = 4, T(ᚠᚢᚦ) = 5, T(ᚠᚦᚢ) = 6, T(ᚠᚦᚦ) = 7$

此時的魔理沙已經掌握前 $N$ 種魔法句子,她想要詠唱其中的 $M$ 個魔法句子 $K_i$,請問她最少需要花費多少點魔力?

Input Format

第一行為兩個整數 $N,M$ $(M \le N,\ 1 \le N \le 10^ 6,\ 0 \le M)$
第二行為 $M$ 個魔法句子編號 $K_i$ $(1 \le i \le M,\ 1 \le K_i \le 10^ 6,\ K_i \le N)$

Output Format

請輸出魔理沙最少要花費多少點魔力來詠唱

Sample Input 1

1 1
1

Sample Output 1

0

Sample Input 2

10 2
2 3

Sample Output 2

2

Sample Input 3

10 2
4 7

Sample Output 3

4

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~20 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 100 65536 65536 1
1 100 65536 65536 1
2 100 65536 65536 1
3 100 65536 65536 1
4 100 65536 65536 1
5 100 65536 65536 1
6 100 65536 65536 1
7 100 65536 65536 1
8 100 65536 65536 1
9 100 65536 65536 1
10 200 65536 65536 1
11 200 65536 65536 1
12 200 65536 65536 1
13 200 65536 65536 1
14 500 65536 65536 1
15 100 65536 65536 1
16 100 65536 65536 1
17 100 65536 65536 1
18 100 65536 65536 1
19 100 65536 65536 1
20 100 65536 65536 1