提示: 欢迎访问OurACM平台。
Problem 2197 最小花费

Accept: 221    Submit: 524
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给一个长度为n(n <= 10^5)的“01”串,你可以任意交换一个为0的位和一个为1的位,若这两位相邻,花费为X,否则花费为Y。求通过若干次交换后将串中的“1”全部变换到“0”前面的最小花费。

Input

第一行一个整数T(1 <= T <= 10),表示测试数据的组数。接下来3*T行,每组数据三行,第一行为整数X(1 <= X <= 10^3),第二行为整数Y(X <= Y <= 10^3),第三行是“01”串。

Output

最小花费。

Sample Input

2 1 2 1100 1 2 0011

Sample Output

0 3

Source

福州大学第十二届程序设计竞赛

Submit  Back  Status  Discuss