问题描述

你正在玩"养懒猫"的教程。教程中讲述了你是如何收养懒猫先生的。

因为迟到，午餐洒了一地，编写的程序到处都是错误，最后还叫前辈"爸爸"......沮丧地你在一个荒凉的黑暗小巷里听到了"喵喵"的声音。

起初，你决定无视它，但第二天、第三天，你依然在同一个地方听到同样的声音。

你好奇地靠近声音的方向。在草丛中展开的景象......无需解释。

就这样，你和懒猫先生的共同生活开始了！

而这已经是你看到这样温馨故事的第10次了。在"养懒猫"中，你可以获得一个随机的游戏道具"猫薄荷"，所以你决定重新开始教程，直到获得自己喜欢的"猫薄荷"。

由于完全记住了故事的内容，你决定专注快速完成教程。

教程分为N个阶段。每个阶段可以是"加载"或"故事"之一，字符串S的第i个字符为0表示第i个阶段为"加载"，为1表示第i个阶段为"故事"。此外，第i个阶段所需时间最初为Ti秒。

在"故事"阶段，你可以按下跳过按钮来在开始后X秒钟之内结束该故事。如果不按下跳过按钮，则此故事的持续时间仍为Ti秒。在"加载"阶段，无法加快进度。

当适当地按下按钮时，你最少需要多少秒才能完成教程呢？

约束条件

• $1 \leq N \leq 1000$
• $1 \leq X \leq 10^6$
• 字符串S的长度为N
• $1 \leq T_i \leq 10^6(1\leq i\leq N)$
• N,X,Ti(1\leq i\leq N)都是整数

输入

输入从标准输入中接收，具体格式如下：

N X S T_1 : T_N

输出

输出教程的最短完成时间。

输入示例1

3 5
011
8
10
3

输出示例1

16

选择第二阶段跳过按钮，在第三阶段不选择跳过按钮的情况下，教程总共需要8+5+3=16秒完成。

输入示例2

5 314
10101
159
265
358
979
323

输出示例2

2031