配点 : 200 点
問題文
您正在玩“Snuke Sodate”教程。在本教程中,我们将告诉您如何选择《Snuke》。
你开学迟到了,你的午餐被打翻了,你写的程序充满了Bug,你最后还喊学长“爸爸”……你发现自己陷入了失望的深渊,发现自己身处黑暗、荒凉的小巷。 我听到喵喵声或小声音。
起初你决定忽略它,但第二天和后天,你在同一个地方听到了同样的声音。
出于好奇,你走近了声音的方向。草丛中蔓延的景象……无需解释。
就这样,你和Nuke君的生活开始了!
我迫不及待地想看到这样温馨的故事。 这是 10 时间。在《Snuke Sodate》中,一开始你会收到一个随机游戏物品“Actatabi”。 原因是您决定重复教程,直到获得您喜欢的“Actatabi”。
现在您已经完全记住了故事,您决定集中精力快速完成教程。
教程是
它分为N 阶段。每个阶段要么是“加载”,要么是“故事”,并且是一个字符串 S 的 i 第一个字母是
当 0 什么时候 i 该阶段正在“加载”,1 什么时候 i 表示第 阶段是“故事”。另外,i 第一阶段所需时间为 T_i 秒。
在“故事”阶段,您可以在故事开始后立即按下跳过按钮来跳过故事。 X 秒内完成它。如果你不按跳过按钮, 这个故事需要多长时间? 仍保持 T_i 秒。在“加载”阶段您无法加快进度。
如果您正确按下按钮,完成教程最少需要多少秒?
制約
- 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,T_i(1\leq i\leq N) 是一个整数
入力
输入将以以下格式从标准输入提供。
N X S T_1 : T_N
出力
打印完成教程所需的最短时间。 在第
入力例 1
3 5 011 8 10 3
出力例 1
16
2 阶段选择跳过, 如果在第3 阶段没有选择“跳过”, 您可以在8+5+3=16 秒内完成本教程。
入力例 2
5 314 10101 159 265 358 979 323
出力例 2
2031