题目描述

机房中有一棵高度为 $h$ 的满二叉树（包含 $2^h$ 个叶结点），传说是某 i 姓同学被吊打过的地方。在这棵树上，我们将所有叶子结点从左往右依次编号为 $1,\ldots,2^h$。其中有 $m$ 个叶 子结点称为关键结点，它们的编号依次为 $t_1,\ldots,t_m$。这棵树上的每个非叶结点上有一个 开关，开关有左右两种状态。接下来执行如下的投球过程：一个球从根结点出发，每次走到当前结点开关指向的那个儿子处，直到走到叶结点，此时该球将会计入该叶结点的球数中，然后，这个球经过的所有结点的开关状态将取反（左变右，右变左）。你可以设置每个开关最初的位置，然后连续投下 $n$ 个球，你需要使得最终所有关键结点的球数之和最大，只需要输出这个最大值。

输入格式

第一行：三个整数 $h, m, n$，分别表示二叉树的深度，关键结点的数量以及投球数。

第二行：$m$ 个整数 $t_{1\ldots m}$，表示关键结点的编号。

输出格式

输出一行一个整数，表示所有关键结点的球数之和的最大值。

样例

2 3 3
1 2 3

3

如图，按最左图安排初始时非叶结点的开关方向（红实线为开关方向），前三个球分别落到 $1, 3, 2$ 这三个点。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le h\le 60$，$1\le m\le \min(2^h,10^5)$，$1\le n\le 10^{18}$，$1\le t_i\le 2^h$ 且 $t_i$ 两两不等。