题解

题面描述

给定一个长度为 $n$ 的数组 $a$ 以及一个长度为 $n$ 的仅由字符 $'0'$ 和 $'1'$ 组成的字符串 $s$。每个位置 $i$ 对应一个操作符：

• 若 $s_i = '1'$，则 $op(i)=1$；
• 若 $s_i = '0'$，则 $op(i)=-1$。

我们可以将数组切分为至多 $k$ 块（也就是最多有 $k-1$ 个切割点）。对于数组中每个位置 $i$，若其所在块的编号为 $j$（块的编号从 $1$ 开始），则该位置的贡献为

题目内容

小红有一个长度为$n$的数组$a$和一个度为n的字符串$s$。她最多可以将数组切割成$1$块。

定义数组的权值为所有元素的权值之和。对于数组中的第$1$个元素，其权值计算方式为：$op(i)×(a+j)$

$op(i)$的值取决手字符串$s$的第$i$个字符:

• 若$s_i$='$1$'，则$op(i) =1$

• 若$s_i$='$0$’，则$op(i)=-1$

• $j$表示$a_i$所在的块的编号(从$1$开始)

小红想要通过合理的切割方式，使得数组的总权值最大，请你帮她计算出可能的最大权值。

输入描述

第一行包含两个正整数$n$和$k$，表示数组的长度和数组最多的块数。

第二行包含n个整数$a_1,a_2，...a_n$，表示数组$a$

第三行包含一个长度为$n$的字符串$s$，仅由字符‘$0$’和'$1$'组成

$1≦k≦n$

$2≤n≤10^5$

$1≤a_i≤10^9$

输出描述

输出一个整数。表示数组可能的最大权值。

样例1

输入

4 2
1 2 3 4
1001

输出

1

说明

一种最优的切割方案是将数组切成$[1,2,3]$和$[4]$两块。