Problem Description

You are playing the tutorial of "Snuke Nurturing". In the tutorial, the story of how you found Snuke is told.

You were late for work, spilled your lunch, your program was full of bugs, and to top it off, you called your senior "Papa"… You were at the lowest point of your despair when you heard a faint meowing in a dark, deserted alley.

At first, you decided to ignore it, but the next day, and the day after that, you heard the same sound in the same place.

Curious, you approached the direction of the sound. The sight that spread in the grass… no explanation is needed.

And so, your co-living with Snuke began!

Seeing this heartwarming story for the 10th time, you decided to restart the tutorial until you get your favorite random game item, "Matatabi".

Having memorized the story completely, you decided to focus on finishing the tutorial quickly.

The tutorial is divided into $ N $ phases. Each phase is either "Loading" or "Story", and the $ i $th character of the string $ S $ being 0 indicates that the $ i $th phase is "Loading", while 1 indicates that the $ i $th phase is "Story". The time taken for the $ i $th phase is initially $ T_i $ seconds.

In a "Story" phase, you can finish the story in exactly $ X $ seconds by pressing the skip button right at the start. If you do not press the skip button, the time taken for this story remains $ T_i $ seconds. In a "Loading" phase, you cannot speed up the process.

When pressing the buttons appropriately, what is the minimum number of seconds needed to finish the tutorial?

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ S $ $ T_1 $ : $ T_N $

Output Format

Output the minimum time required to finish the tutorial.

Sample Input and Output

Sample Input #1

3 5
011
8
10
3

Sample Output #1

16

Sample Input #2

5 314
10101
159
265
358
979
323

Sample Output #2

2031

Notes/Hints

Constraints

• $1 \leq N \leq 1000$
• $1 \leq X \leq 10^6$
• The length of $ S $ is $ N $
• $1 \leq T_i \leq 10^6 (1 \leq i \leq N)$
• $N, X, T_i (1 \leq i \leq N)$ are integers

Sample Explanation 1

By choosing to skip the second phase and not skipping the third phase, you can finish the tutorial in $ 8 + 5 + 3 = 16 $ seconds.

见题面 Input 部分

见题面 Output 部分