You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

千钧之力，汇于一点

题目描述

大自然是很神奇的，包括下面的这棵二叉树。

但是这棵树真实存在吗？我们要对其进行合理性验证，验证的方式为计算树根所承受的重量。

我们定义一个树节点所承受的力 $F_i$ 为它所有子节点的重量$w_{ij}$之和加上该节点自身的重量$w_i$。

但是在不损坏这棵树的前提下，我们只能测量出 $k$ 的幂次倍，其余部分将无法计算。

更准确的说，$F = k^n + p$，其中 $p < k^n$。这个时候 $p$ 将会被丢弃。

因此在每次计算过程中，我们得到的力$F$只能是$k$的幂次倍：$F = k^n$

为了简化问题，现在给你的树都是完全二叉树，1号节点为根节点。

如果该节点的所承受的力已经计算过了，那么我们将使用的是它的所承受的力而不是该节点的重量了。

为了不失一般性，我们默认计算顺序是从叶子节点向根节点计算。

你能知道二叉树根节点所承受的重量吗？

题目格式

输入格式

第一行给你两个以空格间隔的整数 $n,k(n \leq 10^5$，$2 \leq k \leq 10)$ ，其中 $n$ 表示这棵完全二叉树的节点数和。

接下来一行，有 $n$ 个以空格为间隔的数表示第$i$个数为$i$号节点对应的自身重量$w_i(0 \leq w_i \leq 10^8)$。

题目保证$\sum\limits_{i=1}^{n} w_i$ 不超过 long long 范围。

输出格式

仅输出一个数，表示根节点承受的重量。

题目样例

7 2
1 2 3 4 5 6 7

16

样例解释