#XXSY26JBT2. 红军的部队整编

红军的部队整编

红军的部队整编

题目描述

红军模拟演练整编部队,先遣队共有 n 支战斗小组,根据当前装备情况分为两种初始编制:

轻装组,简称“0”型小组。

掩护组,简称“1”型小组。

根据地形侦察报告:

投入一支 “0”型 小组参战,需消耗 a 份后勤补给。

投入一支 “1”型 小组参战,需消耗 b 份后勤补给。

由于战斗需要,可以通过紧急换装(战略转型)来调整编制:将一支“0”型组改造为“1”型组,或将“1”型组改造为“0”型组,均需额外消耗 c 份补给。

请你计算出:在确保所有 n 支小组都投入战斗的前提下,如何通过“直接参战”或“转型后参战”的决策,使总的补给消耗降到最低?

输入格式

第一行包含一个整数 T,表示共有 T次模拟演练。

每组演练包含两行数据:

第一行四个整数 n,a,b,c。

第二行一个长度为 n的 01 字符串,表示各小组的初始编制状态。

输出格式

​ 每组数据结果占一行,输出一个整数表示最小消耗。

输入输出样例

3
4 1 2 1
1001
6 1 1 1
101011
3 2 1 3
111
6
6
3

4
4 3 2 1
1111
7 1 4 2
0111011
5 11 5 1
10010
6 1 1 1
101001
8
17
28
6

数据规模与约定

对 70%的数据保证:1≤T≤10,1≤n,a,b,c≤1000;

对 100% 的数据保证:1≤T≤100,1≤n,a,b,c≤10000。