P12354 「HCOI-R2」秋殇别恋

“你能爱我三天吗？” “哪三天？” “今天，明天......” “和每一天。”

小 $ \zeta $ 在给学弟出校内模拟赛的签到题时，因为出不出来一道送分的可爱签到题沉沉睡去，他梦到了这么一道题： > 有长度为 $ n $ 的序列 $ a,b $，对于 $ 1 \le i \le n $，$ a_i $ 的值给定，$ b_i $ 初始时均为 $ 0 $。你需要支持以下操作 $ m $ 次： > > * `l r v` 表示先算出 $ v'=v(1-\max_{i=l}^r|b_i|) $，对于 $ l \le i \le r $，$ b_i \leftarrow b_i+v' $。 > > $ m $ 次操作后你需要输出 $ \sum_{i=1}^na_ib_i $。 他感觉这道题很有意思，于是下载了这道题的数据包并查看，但是，因为早六的起床铃声，他忘记了每次操作分别的 $ v $ 值和操作的相对顺序，但是他知道，且每次操作的 $ v $ 值都满足 $ v\in\{-1,1\} $。 他决定找到一种还原这道题数据并加以适当的修改的方法使得最后输出的答案最大。修改是关于这道题目中操作的区间范围的，他允许自己进行**最多** $ k $ 次如下操作： * 选定 $ 1 \le i \le m $，进行 $ l_i \leftarrow l_i-1 $、$ l_i \leftarrow l_i+1 $、$ r_i \leftarrow r_i-1 $、$ r_i \leftarrow r_i+1 $ 四种操作中的一种。**且始终保证 $ 1 \le l_i \le r_i \le n $**。 请你求出按照以上要求还原并修改这道题数据的方案中，最大的输出答案。 为了方便你完成这个任务，小 $ \zeta $ 贴心的告诉你了一个很有用的性质：**所有给出的操作区间在还原前互不严格包含**（即不存在 $ 1 \le i,j \le m $ 使得 $ l_i

无

无

### 样例解释 1 * 把区间 $ [2,3] $ 移动到 $ [3,4] $，消耗 $ 2 $ 次修改次数； * 按照参数组 $ (3,4,-1),(1,1,1) $ 的顺序操作，答案最大值为 $ 8 $。 ### 样例解释 3 * 把区间 $ [2,5] $ 移动到 $ [3,5] $，消耗 $ 1 $ 次修改次数。 * 把区间 $ [6,7] $ 移动到 $ [7,10] $，消耗 $ 4 $ 次修改次数。 * 按照参数组 $ (3,5,-1),(2,3,1),(1,2,1),(7,10,-1) $ 的顺序操作，答案最大值为 $ 38 $。 ### 数据规模与约定 **本题采用捆绑测试。** | 子任务编号 | $ n \le $ | $ m \le $ | $ k \le $ | 分值 | |:-:|:-:|:-:|:-:|:-:| | $ 0 $ | $ 10 $ | $ 5 $ | $ 5 $ | $ 10 $ | | $ 1 $ | $ 10^3 $ | $ 100 $ | $ 1 $ | $ 15 $* | | $ 2 $ | $ 20 $ | $ 5 $ | $ 20 $ | $ 15 $ | | $ 3 $ | $ 100 $ | $ 10 $ | $ 100 $ | $ 30 $ | | $ 4 $ | $ 10^3 $ | $ 100 $ | $ 10^3 $ | $ 30 $ | \*：子任务 $ 1 $ 测点等分加和，其中存在 $ 5 $ 分的测试点满足 $ k=0 $。 对于所有数据，$ 1 \le n \le 1000 $，$ 1 \le m \le 100 $，$ 0 \le k \le 1000 $，$ 0 \le |a_i| \le 10^6 $，对任意 $ 1 \le i \le m $ 有 $ 1 \le l_i \le r_i \le n $，**不存在 $\boldsymbol{ 1 \le i,j \le m }$ 使得 $\boldsymbol{ l_i