题目描述

这是一个充满爱的村子，它的名字叫二重镇。在这个爱意浓浓的村子里，居民们的生活快乐又安宁。二重镇呈长条形状，可分为排成一行的 $N$ 个方格。每个格子可能是空地，也可能是小草、灌木、大树、房屋或城堡中的一种物品。每种物品都有一个等级，小草的等级是 $1$，灌木的等级是 $2$，依此类推。

你是这个村庄的建造者。你会陆续获得 $D$ 件物品，你要将它们合理地放置在村庄的空地上。你的目标是要让村子的总人气尽可能大。人气的获得规则在后面说明。关于放置的规则有以下几条：

• 第一，每件物品都必须放在一个地方，不可丢弃，如果没有空地了，游戏直接结束；

• 第二，物品可以放在一格空地上，或者临时放在仓库里。仓库同时最多只能放一件物品，它一开始是空的。只存在一个仓库；

• 第三，一旦物品放在某个空格上，只要符合条件，系统就会自动将一些物品合成一个大的物品，这是强制被动的，也是瞬间的。直到合成结束后，才能放置下一个物品。

• 第四，存放在仓库中的物品，随时可以取出放到空地上（但注意不能在合成的过程中放置），也可以一直留在仓库里。

• 第五，除非利用仓库，不然不能更改物品的放置顺序；

总结起来，这个游戏的流程就是获得一个新物品，决定是否将这个物品存入仓库，再决定将仓库中的物品或新物品放到哪个空地上，系统自动判定合成，获得人气，直到所有物品都被放置完毕，或空地用完为止。

最后是关于合成的规则。合成是自动完成的，也是强制性的。如果有连续两个或以上相邻的格子里有相同等级的物品，它们会自动合体成一个新的物品，新物品的等级比之前高一个级别。合体分三步：

• 第一步，确定有多少物品参与合成，这些物品的位置必须连在一起，等级相同。参与合体的物品会全部消失，对应的格子边成空地；

• 第二步，假设有 $A$ 个 $K$ 级物品参与合体，那么将获得$A\times 2^K$ 点人气。例如有一次五棵小草进行了合体，那么总人气就会增加 $5 \times 2^1=10$；

• 第三步，一个 $K+1$ 等级的物品会出现在一个格子里。如果 $K+1$ 大于 $5$，则跳过这步，但第二步中的人气仍然要算，第一步中的旧物品也会被清除。这个高等级的物品只会出现在参与合体的格子上。每个格子会记录最后一次被放置物品的时间，新的物品会出现在该时间最晚的那个格子里，形象地说，就是出现在最近被放置过东西的格子；

最后，请注意合成是会触发多次的，比如两个小草合成一个灌木，如果这棵灌木旁边还有其他灌木，合体将继续发生下去。

现在，给出 $N$ 和获得物品的顺序及等级，请你要合理地将这些物品放置在一个初始全是空地的村子里，使得村子最终的人气值尽可能高。当所有物品都被放置，或者某一刻村子里没空地了，你都会结束村子的建设，而此时村子里累计人气值就是你的最终成果。

输入格式

第一行给出两个整数 $N$ 和 $D$，用空格隔开。$N$ 表示村庄大小，$D$ 表示建设村庄的天数。

第二行为一个字符串，每个字符为 $1 \ldots 5$ 之间的一个字符，表示每天你可以放置的物品的等级。

输出格式

输出一个整数，表示你能得到的最大的人气值。

4 10
1132411235

168

数据规模与约定

• 对于 $30\%$ 的数据，$N=3$, $D\leq 10$。
• 对于 $60\%$ 的数据，$N\leq 4$, $D\leq 30$。
• 对于 $100\%$ 的数据，$N\leq 6$, $D\leq 100$。