Tree compression

The team of professor Fabinaris Suchbaum in Max Planck Institute for Software Systems in SaarbrĂźcken, Germany, who are famous worldwide for their breakthrough contributions to tree-related computer data structures are working on a new exciting project. You can read about some of the team's earlier successes here and here and here and here and here and here and here.

This time, the team is developing a tree coding method. They have found out that many rooted trees of big size, even infinite trees, can be completely described and encoded by just a few small integer numbers. This may lead to many novel and highly efficient compression algorithms in the future and the team is eager to study the proposed method in more detail.

We remind the reader that the degree of a node is the number of its children. The method works as follows:
In each depth of a given tree, except for the biggest depth, all node degrees are listed in the order from left to right.
Then, these lists of degrees are concatenated into one long list in the order of increasing depth. This new list is called an extended sequence of the tree.
Note that the tree edges can be unambiguously reconstructed from its extended sequence.
Another sequence is also associated with the tree, it is called a core sequence of the tree. Usually, it is much shorter than the extended sequence. The extended sequence is related to the core sequence by the simple rule:

• Let the N1 be the number of nodes in the tree minus the number of nodes in the biggest depth of the tree. Concatenate the core sequence with itself repeatedly, until its length it at least N1. The subsequence of the first N1 elements in the concatenated core sequence is exactly equal to the extended sequence.

Thus, it is possible to reconstruct the tree edges when only the depth and the core sequence of the tree are given.

To draw more attention to their activities, the researches decided to hire an artist who would construct a physical model of a tree and install it in the entrance hall of the institute.
The nodes of the model tree, small polished molybdenum balls, will be attached to a vertical wall in the entrance hall, with the root located at the top. Nodes in the same depth in the tree will be in the same height above the floor. The distance between two neighbour nodes in the same depth will be always 2 units and also the distance between two consecutive levels of depth will be always 2 units. To keep the image of the tree optically balanced an appealing, additional symmetry will be defined by an imaginary vertical axis going through the center of the root. Nodes in each level will be arranged symmetrically with respect to the axis. In each depth, the number of nodes located to the left of the axis and the number of nodes located to the right of the axis will be the same. When the number of nodes in a particular depth will be odd, the center of one of the nodes will be located exactly on the axis.
When a node b will be situated to the right of node a in the same depth, then any child of b will be situated to the right of any child of a in the next depth, providing those children will exist.
Note that two neighbour nodes in the same depth need not be necessarily the children of the same parent.

In the model tree, the connections between the nodes are coded in the way proposed by the team. A plaque containing the tree core sequence and the depth of the tree will be attached to the model too.
The nodes, represented by the balls in the model, will be connected by edges made of special wire. The wire is another current breakthrough in the optical ceramic matrix composites and it has to be manufactured in appropriate length to fit the model demands. It is presumed that the length of each peace of wire connecting two balls will be exactly equal to the distance between the centers of the balls.
The total length of the wire has to be calculated in advance.

Image 1. An example of a tree T with 52 nodes. The depth of T is 10. The core sequence of T is (2, 1, 3, 0, 1, 0, 2). The extended sequence of T is (2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0, 2, 1, 3, 0, 1, 0 ). The layout of T in the image reflects the tree layout on the entrance hall wall. The total length of the wire rounded to the nearest bigger integer is 133. The image depicts the data of Example 1 below.

The task

You are given the core sequence of a tree and its depth. Compute the total length of all edges in the layout of the tree on the entrance hall wall.

---

Input

The first input line contains two integers L and D representing the length of the core sequence and the depth of the resulting tree.
The next line contains L integers, separated by spaces, representing the core sequence itself.
It holds, 1 ≤ L ≤ 10, 2 ≤ D ≤ 60, all values in the core sequence are non-negative and less than 10.

Output

The output contains one text line with one integer, the total length of all wires, representing the edges in the tree model, rounded up to the nearest bigger integer.
Output the result as a plain integer, without decimal separator and with no decimal digits.
The result is guaranteed to be smaller than 10¹¹.

Example 1 Input 6 10 2 1 3 0 1 0 Output 133

Image 2. The tree in Example 1. It is also depicted in Image 1.

Example 2 Input 8 12 2 1 2 0 2 0 0 1 Output 54

Image 3. The tree in Example 2.

Example 3 Input 2 3 5 2 Output 1251

Image 4. The tree in Example 3.

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set