This is a village full of love, named Triple Town. In this love-filled village, the residents live a happy and peaceful life. The village is shaped like a long strip and can be divided into $N$ squares arranged in a row. Each square can be an empty space, or one of the following items: grass, bush, tree, house, or castle. Each item has a level: grass is level 1, bushes are level 2, and so on.

You are the builder of this village. You will receive $D$ items one after another, and you must place them reasonably in the empty spaces of the village. Your goal is to make the total popularity of the village as high as possible. The rules for gaining popularity are explained later. The rules for placement are as follows:

1. Every item must be placed in a location and cannot be discarded. If there are no empty spaces left, the game ends immediately.
2. An item can be placed in an empty square or temporarily stored in a warehouse. The warehouse can hold at most one item at a time and is initially empty. There is only one warehouse.
3. Once an item is placed in an empty square, if the conditions are met, the system will automatically merge some items into a larger item. This is mandatory, passive, and instantaneous. You cannot place the next item until the merging process is complete.
4. Items stored in the warehouse can be taken out and placed in an empty square at any time (note that they cannot be placed during the merging process), or they can remain in the warehouse indefinitely.
5. Unless you use the warehouse, you cannot change the order in which items are placed.

In summary, the flow of the game is: receive a new item, decide whether to store it in the warehouse, then decide which empty square to place the item from the warehouse or the new item into. The system automatically determines if a merge occurs and awards popularity, until all items are placed or the empty spaces are exhausted.

Finally, regarding the rules for merging: Merging is automatic and mandatory. If there are two or more adjacent squares containing items of the same level, they will automatically merge into a new item, and the new item's level will be one higher than the previous level. The merging process consists of three steps:

1. Determine how many items are involved in the merge. These items must be adjacent and have the same level. All items involved in the merge will disappear, and the corresponding squares will become empty.
2. Suppose $A$ items of level $K$ are involved in the merge, then you will gain $A \times 2^K$ popularity. For example, if five pieces of grass are merged, the total popularity will increase by $5 \times 2^1 = 10$.
3. A level $K+1$ item will appear in one of the squares. If $K+1$ is greater than 5, this step is skipped, but the popularity from the second step is still counted, and the old items from the first step are still cleared. This higher-level item will only appear on one of the squares that participated in the merge. Each square records the time when an item was last placed in it; the new item will appear in the square with the latest timestamp—figuratively speaking, it appears in the square where something was most recently placed.

Finally, please note that merging can be triggered multiple times. For example, if two pieces of grass merge into a bush, and there are other bushes next to this bush, the merging will continue.

Given $N$ and the sequence and levels of the items received, you need to reasonably place these items in a village that is initially all empty to maximize the final popularity value of the village. When all items have been placed, or at any moment when there are no empty spaces left in the village, you will end the construction of the village, and the accumulated popularity at that time is your final result.

Input

The first line contains two integers $N$ and $D$, separated by a space. $N$ represents the size of the village, and $D$ represents the number of days to build the village.

The second line is a string, where each character is between '1' and '5', representing the level of the item you can place each day.

Output

Output a single integer representing the maximum popularity you can obtain.

Examples

Input 1

4 10
1132411235

Output 1

168

Constraints

For 30% of the data, $N=3$, $D \le 10$. For 60% of the data, $N \le 4$, $D \le 30$. For 100% of the data, $N \le 6$, $D \le 100$.