题目描述

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

定义数组的权值为所有元素的权值之和。对于数组中的第$1$个元素，其权值计算方式为：$op(i)\times (a+j)$，其中$j$表示$a_i$所在的块的编号(下标从$1$开始)

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

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

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

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

输入描述

第一行包含两个正整数$n,k(1\le k\le n\le 10^5)$，表示数组的长度和数组最多的块数。

第二行包含$n$个整数$a_1,a_2,...a_n(1\le a_i\le 10^9)$，表示数组$a$

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

输出描述

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

样例1

输入

4 2
1 2 3 4
1001

输出

1

样例解释

一种最优的切割方案是将数组切成$[1,2,3]$和$[4]$两块。对应的权值为$1\times (1+1)+(-1)\times (2+1)+(-1)\times (3+1)+1\times (4+2)=1$