D - 虫歯(Cavity) Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

kyuridenamidaは, お菓子を食べ過ぎて1本の歯を虫歯にしてしまった.
その歯がとても痛むので歯医者さんに治療してもらったところ, 歯の神経のうち N 箇所を治療してもらえた.

kyuridenamidaの歯の神経は, 図1に示すように, 深さがKの完全二分木になっている.
(二分木については, Wikipediaのページなどを参照せよ.)

図 1

彼の神経を表す二分木で, 深さが i で左から j 番目の神経を (i,j)と表す(図 2 ).
このとき, 根に当たる神経 (0,1) に, 先祖を遡ってたどり着ける神経を, 虫歯神経と呼ぶこととする.
ただし, 虫歯神経の先祖が既に治療されている場合, その虫歯神経は根の神経 (0, 1) に辿りつけない.
また, (0, 1)自身が治療されていなければ, (0, 1) が自身にたどり着けるものとする.

図 2

根に辿り着ける虫歯神経の個数の総和を歯の痛みとする.
あなたの仕事は, kyuridenamidaの虫歯の情報が与えらるので, その歯の痛みをkyuridenamidaに教えて上げることである.

入力

K
N
p_1 q_1
p_2 q_2
.
.
.
p_N q_N
  • 1 行目には, 神経の深さを表す整数Kが書かれている.
  • 2 行目には, 治療された神経の数を表す整数Nが書かれている.
  • 続く N 行には, 治療済みの神経の情報をあらわす, 整数 p_iと q_i (1 ≦ i ≦ N) が空白区切りで書かれている.
    これは, 場所 (p_i,q_i) の神経が治療されていることを表す.

出力

痛みを伝える神経の数を, 1 行に出力せよ.
(答えが 32 bit整数型に収まらない可能性があることに注意せよ.)

制約

  • 1 ≦ K ≦ 50　歯の神経の深さ
  • 0 ≦ N ≦ 10^5　治療済みの神経の個数
  • 0 ≦ p_i ≦ K 　治療済み神経 i の深さ
  • 1 ≦ q_i ≦ 2^{p_i}　治療済み神経 i の, 深さ p_iでの位置
  • p_i = p_j であれば, q_i ≠ q_jが保証されている.

部分点

配点の 40% 分については, N ≦ 1000 を満たす.

入力例 1

1
1
1 1

出力例 1

2

入力例 2

9
0

出力例 2

1023

入力例 3

3
2
1 2
3 7

出力例 3

8

ヒント

入出力例3に対応する図は以下のとおりである.
ここで, 図の青丸は治療された神経を表し, 赤の×印は根に辿り着ける虫歯神経を表す.
(Story) kagamiz
(Problem) kagamiz
(Tester) fura2