← 返回题目列表

AtCoder · colopl2018_qual_b

B. Snuke Stand--教程-

中文机器翻译题面 查看原题

配点 : 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