XiaoXi has been on frequent
business trips recently, but she always flies between the two cities (A and B).
In order to simplify the problem,
we simplify Xiaoxi's future business trip sequence (in chronological order)
into a 01 string. If i-th position of string is 1 represents that she will fly
from city A to city B, and 0 represents that she will fly from city B to city A.
As we all know, the price of air
tickets is expensive. Xiaoxi knows four values, namely, the price of an one-way
ticket from A to B, and the price of A to B round trip ticket (including A to B
and B to A, which need not be continuous, but A to B must be used before taking
B to A ticket), the price of one way ticket from B to A, and B to A round trip
ticket price .
Ticket prices will not change.
Xiaoxi hopes to complete his business trip at the cheapest price.
输入格式:
The first line contains an
integer T to denote the number of data cases (T<=100).
The first line of each case of
data is input with a string S, which represents Xiao Xi's future travel
sequence(01 string).
The second line enters four
integers, representing the price of one-way ticket from A to B, the price of round
trip ticket from A to B, the price of one-way ticket from B to A, and the price
of round trip ticket from B to A, all of which are less than 1000000.
1 <= |S| <= 100000 (the
length of S)
Σ|S| <=
1000000
输出格式:
For each testcase, print an integer
respecting your answer in one line.
