B - 虫歯(Cavity) Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

※20:22現在, セット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)

※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。
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