Description

This is a village full of love, called Double Town. In this affectionate village, the residents live happily and peacefully. Double Town is long and narrow and can be divided into a row of $N$ cells. Each cell may be empty, or contain exactly one of the following: grass, shrub, tree, house, or castle. Each type has a level: grass has level $1$, shrub has 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 properly on empty cells. Your goal is to maximize the village’s total popularity. The rules for gaining popularity are explained later. The placement rules are as follows:

• First, every item must be placed somewhere and cannot be discarded. If there is no empty cell, the game ends immediately.
• Second, an item can be placed on one empty cell, or temporarily stored in the warehouse. The warehouse can hold at most one item at a time, and it is initially empty. There is only one warehouse.
• Third, once an item is placed on a cell, as long as conditions are met, the system will automatically merge some items into a larger item. This is mandatory, passive, and instantaneous. Only after merging finishes can you place the next item.
• Fourth, an item stored in the warehouse can be taken out and placed on an empty cell at any time (but not during a merge), or it may remain in the warehouse.
• Fifth, unless you use the warehouse, you cannot change the order in which items are placed.

In summary, the process is: when you receive a new item, decide whether to store it in the warehouse, then decide where to place either the warehouse item or the new item on an empty cell, the system automatically performs merges and awards popularity, and you continue until all items have been placed or there are no empty cells left.

Finally, here are the merge rules. Merging is automatic and mandatory. If two or more consecutive adjacent cells contain items of the same level, they will automatically merge into a new item whose level is one higher. A merge proceeds in three steps:

• Step 1: Determine how many items participate in the merge; these items must be contiguous and of the same level. All participating items disappear, and their cells become empty.
• Step 2: Suppose $A$ items of level $K$ merge. You gain $A\times 2^K$ popularity. For example, if five grasses merge once, the total popularity increases by $5 \times 2^1=10$.
• Step 3: One item of level $K+1$ appears in one cell. If $K+1$ is greater than $5$, skip this step, but you still gain the popularity from Step 2, and the old items from Step 1 are still removed. The higher-level item appears only on one of the participating cells. Each cell records the time when an item was last placed on it; the new item appears on the cell with the latest such time—in other words, on the cell most recently placed upon.

Finally, note that merges may be triggered multiple times. For example, two grasses may merge into a shrub; if that shrub is adjacent to other shrubs, merging continues.

Given $N$ and the sequence and levels of the items you receive, arrange them on an initially all-empty village to maximize the final total popularity. When all items have been placed, or at any moment when there are no empty cells, construction ends, and the accumulated popularity at that time is your final score.

Input Format

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

The second line is a string, each character between $1 \ldots 5$, indicating the level of the item you can place each day.

Output Format

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

4 10
1132411235

168

Hint

For $30\%$ of the testdata, $N=3$, $D\leq 10$.

For $60\%$ of the testdata, $N\leq 4$, $D\leq 30$.

For $100\%$ of the testdata, $N\leq 6$, $D\leq 100$.

Translated by ChatGPT 5