1169: Kitty猫基因突变
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：2
题目描述
学习完基础生物基因学之后，小可可再接再厉，又接着选修了生物基因工程学。小可可至今还清楚地记得学习基础生物基因学的时候，教授提出的ABC编码方案是不断地按照对Kitty猫基因01串表达式s进行改写，直至最终被改写成只含有字符“A”、“B”、“C”的符号串。
学习过程中，小可可协助教授做了一些基因突变育种的工作。但是实验过程中，小可可越来越佩服教授先前提出的基因编码方案，因为恰好基因ABC编码的长度说明了Kitty猫的品种优良程度，其ABC编码长度越短，品种越优良。
教授有一套神秘的技术手段让Kitty猫基因的各个位置上的基因单元都能够单独地发生突变；但是由于技术手段还不足够先进，每次实验都恰好使w个基因单元0同时突变成基因单元1，而基因单元1不论在什么位置都不可能发生突变。
教授考察了各种不同的Kitty猫，发现SuperSamuel星球上原有的各种Kitty猫的基因中都至少有w个基因单元0。
而且经研究发现：在不同的位置上发生突变的成本ci是不同的，而基因s突变成s'的成本C(s,s')就是发生突变的那些基因单元的突变成本的总和。
同时，由于实验室经费不足，教授没有足够多的经费来培育出w个基因单元0同时发生突变所能得到的最优良品种。为此，他只能以粗略地以突变成本C(s,s')+突变后基因的ABC编码长度T(s')为评价指标A(s,s')来确定将培育出的新品种，A(s,s')越小，其评价效果越好。教授总是培育出评价效果最好的那些突变品种。
例如，k=3，即s串长度为2^3；c1、c2、…、cn依次是10、10、5、6、3、2、1、2；w=2，即恰好每次都是2个基因单元0同时发生突变。此时基因的01串表达式s=11000101中的第三、四、五和第七个基因单元都是0。
有一种突变方案是第三个和第四个基因单元发生突变，突变后基因的01串表达式s1'=11110101。因此其突变成本C(s,s')=c3+c4=5+6=11；其ABC编码T(s'I)=CBCCABCAB，编码长度是9。所以突变后得到的新品种的评价指标值A(s,s')=11+9=20。
另外一种突变方案是第五个和第七个基因单元发生突变，突变后基因的01串表达式s'II=11001111。因此其突变成本C(s,s'II)=c5+c7=3+1=4；其ABC编码T(s'II)=CCBAB，编码长度是5。所以突变后得到的新品种的评价指标值A(s,s'II)=4+5=9。
显然后一种方案的评价效果要比前一种方案好。
经过计算，同时突变两个基因单元的各种方案中评价效果最好的方案就是同时突变第五个和第七个基因单元的方案。
现在请你编写程序帮小可可找出评价效果最好的突变方案。
学习过程中，小可可协助教授做了一些基因突变育种的工作。但是实验过程中，小可可越来越佩服教授先前提出的基因编码方案，因为恰好基因ABC编码的长度说明了Kitty猫的品种优良程度，其ABC编码长度越短，品种越优良。
教授有一套神秘的技术手段让Kitty猫基因的各个位置上的基因单元都能够单独地发生突变；但是由于技术手段还不足够先进，每次实验都恰好使w个基因单元0同时突变成基因单元1，而基因单元1不论在什么位置都不可能发生突变。
教授考察了各种不同的Kitty猫，发现SuperSamuel星球上原有的各种Kitty猫的基因中都至少有w个基因单元0。
而且经研究发现：在不同的位置上发生突变的成本ci是不同的，而基因s突变成s'的成本C(s,s')就是发生突变的那些基因单元的突变成本的总和。
同时，由于实验室经费不足，教授没有足够多的经费来培育出w个基因单元0同时发生突变所能得到的最优良品种。为此，他只能以粗略地以突变成本C(s,s')+突变后基因的ABC编码长度T(s')为评价指标A(s,s')来确定将培育出的新品种，A(s,s')越小，其评价效果越好。教授总是培育出评价效果最好的那些突变品种。
例如，k=3，即s串长度为2^3；c1、c2、…、cn依次是10、10、5、6、3、2、1、2；w=2，即恰好每次都是2个基因单元0同时发生突变。此时基因的01串表达式s=11000101中的第三、四、五和第七个基因单元都是0。
有一种突变方案是第三个和第四个基因单元发生突变，突变后基因的01串表达式s1'=11110101。因此其突变成本C(s,s')=c3+c4=5+6=11；其ABC编码T(s'I)=CBCCABCAB，编码长度是9。所以突变后得到的新品种的评价指标值A(s,s')=11+9=20。
另外一种突变方案是第五个和第七个基因单元发生突变，突变后基因的01串表达式s'II=11001111。因此其突变成本C(s,s'II)=c5+c7=3+1=4；其ABC编码T(s'II)=CCBAB，编码长度是5。所以突变后得到的新品种的评价指标值A(s,s'II)=4+5=9。
显然后一种方案的评价效果要比前一种方案好。
经过计算，同时突变两个基因单元的各种方案中评价效果最好的方案就是同时突变第五个和第七个基因单元的方案。
现在请你编写程序帮小可可找出评价效果最好的突变方案。
输入
第一行有两个正整数k和w，1≤k≤7，1≤w≤30；第二行存放的是长度为2k的基因01串表达式；第三行有2k个整数，依次为突变成本c1、c2、…、c2^k，1≤ci≤100。
输出
以一行的形式输出评价效果最好的突变方案的评价指标。
样例输入 复制
3 2
11000101
10 10 5 6 3 2 1 2
样例输出 复制
9提示
输入
2 1
0000
3 5 1 4
输出
6
2 1
0000
3 5 1 4
输出
6