あるシステムには、$1$ から $n$ までの番号が付いた $n$ 種類のプログラムがあります。種類 $k$ のプログラムのインスタンスが起動すると、起動時刻を基準として $k$ 秒ごと、具体的には時刻 $k, 2k, 3k, \ldots$ にログを生成します。

時刻 $0$ に、システムは $m$ 個のコマンドを同時に実行します。$i$ 番目のコマンドは、番号が区間 $[l_i, r_i]$ に含まれる各種類のプログラムについて、インスタンスを1つ起動します。複数のコマンドの区間が重なる場合、同じ種類のプログラムのインスタンスが複数起動されることがあり、各インスタンスは独立にログを生成することに注意してください。

システムは、時刻 $1, 2, \ldots, n$ に生成されたすべてのログを記録します。各レコードには、そのログを生成したインスタンスに対応するプログラムの種類の番号だけが含まれます。

あなたの課題は、これらのログを圧縮するアルゴリズムを設計することです。$n$ 種類すべてのプログラムに、識別子として空でない二進文字列を割り当て、どの識別子も他の識別子の接頭辞にならないようにしなければなりません。1つのレコードを符号化するコストは、対応するプログラムの種類に割り当てられた識別子の長さであり、総コストはすべてのレコードのコストの合計です。可能な総コストの最小値を求めてください。

入力

最初の行には2つの整数 $n, m$ ($1 \le n \le 10^{10}$, $1 \le m \le 10^5$) が与えられ、それぞれプログラムの種類の数とコマンドの数を表します。

続く $m$ 行のそれぞれには、起動コマンドを表す2つの整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$) が与えられます。

出力

総コストの最小値を表す整数を1つ出力してください。

入出力例

入力 1

5 1
1 5

出力 1

20

入力 2

6 2
1 3
4 6

出力 2

32

注記

ログは時刻順に記録されるものとします。同じ時刻に生成されたログについては、対応するプログラムの種類の番号の単調非減少順にレコードが並びます。

最初の例では、ログは $[1, 1, 2, 1, 3, 1, 2, 4, 1, 5]$ です。識別子の最適な割り当ての1つは、（プログラム $1$: 0、プログラム $2$: 100、プログラム $3$: 101、プログラム $4$: 110、プログラム $5$: 111）です。コストは $5 \times 1 + 2 \times 3 + 1 \times 3 + 1 \times 3 + 1 \times 3 = 20$ です。

2番目の例では、ログは $[1, 1, 2, 1, 3, 1, 2, 4, 1, 5, 1, 2, 3, 6]$ です。識別子の最適な割り当ての1つは、（プログラム $1$: 0、プログラム $2$: 10、プログラム $3$: 1100、プログラム $4$: 1101、プログラム $5$: 1110、プログラム $6$: 1111）です。コストは $6 \times 1 + 3 \times 2 + 2 \times 4 + 1 \times 4 + 1 \times 4 + 1 \times 4 = 32$ です。