解题思路
本题的核心在于分析划分段数对总效用的影响，并转化为贪心选取最佳切割点的问题。
设极性系数 pi：若 ti=‘1’ 则 pi=1，否则 pi=−1。
对于第 j 段中的第 i 颗宝石，贡献为 pi×(vi+j)。
1. 基础效用计算
若不进行任何划分（即所有宝石属于同一段，段编号 j=1），总效用为：
题目内容
作为一名珠宝工匠，你有一串共 n 颗宝石。每颗宝石有一个基础价值 vi 和一个极性标记。极性标记由一个长度为 n 且仅包含字符 0 和 1 的字符串 t 给出。对于第 i 颗宝石，若 ti 为 1，则其极性系数 pi=1；若 ti 为 0，则 pi=−1。
你需要将宝石序列顺次划分为至多 k 个连续非空段，每段将被加工成一件首饰。首饰按顺序编号 1,2,…。对于第 j 段中的第 i 颗宝石，它对总效用的贡献为 pi×(vi+j)。总效用为所有宝石贡献之和。
你可以自由选择划分方案，目标是最大化总效用。请求出这个最大总效用。
数据范围：宝石个数 n 满足 2≤n≤105，最多段数 k 满足 1≤k≤n。所有基础价值 vi 均满足 1≤vi≤109。字符串 t 的长度为 n，仅由字符 0 和 1 构成。
输入描述
