AT_k2pc001_e4.虫歯(Cavity)

kyuridenamida 因为吃了太多零食，导致一颗牙齿蛀坏了一根神经。
由于这颗牙齿非常疼痛，他去看了牙医，牙医帮他治疗了牙齿神经中的 $N$ 个部位。

kyuridenamida 的牙齿神经如图 $1$ 所示，是一棵深度为 $K$ 的完全二叉树。
（关于二叉树，可以参考 Wikipedia 页面 等。）

图 $1$

在表示他神经的二叉树中，深度为 $i$、从左到右第 $j$ 个神经记作 $(i, j)$（见图 $2$）。
此时，能够通过祖先一路向上到达根节点 $(0, 1)$ 的神经，被称为虫牙神经。
但是，如果某个虫牙神经的祖先已经被治疗，则该虫牙神经无法到达根节点 $(0, 1)$。
另外，如果 $(0, 1)$ 本身没有被治疗，则认为 $(0, 1)$ 能够到达自身。

图 $2$

能够到达根节点的虫牙神经的总数被称为牙痛值。
你的任务是，根据给定的 kyuridenamida 的虫牙信息，告诉他牙痛值是多少。

请输出能够传递疼痛的神经数量，输出一行。
（注意，答案可能无法用 $32$ 位整数型表示。）

• $1 \leq K \leq 50$ —— 牙齿神经的深度
• $0 \leq N \leq 10^5$ —— 已治疗的神经数量
• $0 \leq p_i \leq K$ —— 第 $i$ 个已治疗神经的深度
• $1 \leq q_i \leq 2^{p_i}$ —— 第 $i$ 个已治疗神经在深度 $p_i$ 时的位置
• 若 $p_i = p_j$，则 $q_i \neq q_j$ 保证不会重复

对于 $40\%$ 的数据，$N \leq 1000$。

1
1
1 1

2

9
0

1023

3
2
1 2
3 7

8

输入输出样例 3 所对应的图如下。
其中，图中的蓝色圆圈表示已治疗的神经，红色叉号表示能够到达根节点的虫牙神经。

第一行包含一个整数 $K$，表示二叉树的深度。
第二行包含一个整数 $N$，表示已治疗的神经数量。
接下来的 $N$ 行，每行包含两个整数 $p_i$ 和 $q_i$，表示第 $i$ 个已治疗神经的位置。

输出一行，表示能够传递疼痛的神经数量。

无。

由 ChatGPT 4.1 翻译