Dual Town Construction

You are the builder for a lovely village called Dual Town. The village is represented as a one‐dimensional grid of N cells (initially all empty) arranged in a row. Each cell may hold one object. There are 5 kinds of objects: grass (level 1), bush (level 2), tree (level 3), house (level 4) and castle (level 5). When several objects of the same level K are placed in consecutive cells, they will automatically merge according to the following rules:

• If A contiguous objects of level K merge, you gain A \( \times 2^K \) popularity points.
• All these objects disappear (their cells become empty).
• If K+1 \le 5, a new object of level K+1 will appear in one of the cleared cells. Specifically, each cell stores the time when an object was last placed there; the new object will appear in the cell with the latest such time in that contiguous block.

You will receive a total of D items one by one (each item has a given level between 1 and 5). For each received item you must do the following:

1. You may decide to store the new item in the warehouse. There is exactly one warehouse that can hold at most one item. (Initially the warehouse is empty.)
2. Then, you must choose an item to place on an empty cell. The only options are:

• If the warehouse is empty, you can only place the new item. You must place it, but you have a choice: either place it directly, or store it in the warehouse and then immediately place it. (Placing the stored item delays consumption of the new item—the item remains available for later turns.)
• If the warehouse is not empty (because you stored a previous new item and haven’t used it yet), you must take the stored item and place it. In this case the new item is not placed and will be available in a subsequent turn.

Important rules:

• You cannot discard any item. If there is no empty cell available when you need to place an item, the construction stops immediately.
• The placement order of items is fixed unless you deliberately use the warehouse to delay (and thus reorder) the arrival.
• After each placement, the merging process is triggered until no further merge is possible.

Your goal is to design a strategy to place the items so that the final total popularity (the sum of all points from merges) is maximized. The process ends either when all items have been placed or when no empty cell remains.

Note: All formulas must be written in LaTeX format. For example, the score obtained by merging \(A\) objects of level \(K\) is \(A \times 2^K\).

inputFormat

The first line contains two integers N and D, where N is the number of cells and D is the number of incoming items. The second line contains D integers. The \(i\)-th integer indicates the level of the \(i\)-th item (each level is between 1 and 5).

outputFormat

Output a single integer representing the maximum total popularity score achievable.

sample

3 3
1 1 1

10