U419508 花店

**时间限制：** 1.0 秒 **空间限制：** 512 MB

小 I 经营着一个花店，其中 $n$ 盆最漂亮的花是非卖品，用于花店的装饰。方便起见，将它们从 $1$ 至 $n$ 编号。第 $i$ 盆花的魅力为 $b_i$ 。 为了迎客，每天小 I 都需要在 $n$ 盆花中选择一盆花摆在店门口。受花期、天气、花的种类的多样性等影响，小 I 已经决定了接下来 $m$ 天里每天摆哪一盆花，其中第 $i$ 天摆第 $a_i$ 盆花。 根据历年来的数据，小 I 预测接下来 $m-k+1$ 天里，第 $j~(1\le j\le m-k+1)$ 天将会有 $c_j$ 位顾客开始关注小 I 的花店。小 I 的花店可以打动某一位顾客，当且仅当 : - 若这个顾客在第 $x$ 天关注小 I 的花店，则在 $x,(x+1),...,(x+k-1)$ 这连续的 $k$ 天里，小 I 的花店每天摆出的花的魅力都大于等于 $V$ ，其中 $V$ 是一个对于所有顾客均相同的给定值。 每有一位顾客被打动，小 I 就会获得 $1$ 的收益。 为了获得更多的收益，小 I 决定今天培养一下这 $n$ 盆非卖品。具体地，小 I 可以花费 $x$ 的代价，将任意一盆花的魅力增加 $x$ ，其中 $x$ 为非负整数。小 I 可以使用这一方法对任意多的花增加魅力。 小 I 想知道，在如上情境下，$m$ 天后他的收益总和减去代价总和最大可以是多少。可是小 I 是花店老板不懂算法，所以需要你来帮忙。

无

无

### 样例 1 解释 将第一盆花的魅力值增加 $1$ ，这样所有 $5$ 个顾客都会被打动，收益为 $5$ ，代价为 $1$ 。容易证明没有更优的方案，因此输出为 $5-1=4$ 。 ### 样例 2 解释 不做任何操作，这样第一天开始关注花店的两个顾客会被打动，而第二天开始关注花店的三个顾客不会。收益为 $2$ ，代价为 $0$ 。容易证明没有更优的方案，因此输出为 $2-0=2$ 。 ### 子任务 对于所有测试数据，$1\le n\le 5000,~1\le k\le m\le 5000,~0\le b_i\le V\le 10^6,~1\le a_i\le n,~0\le c_i\le 10^7,~\sum\limits_{i=1}^{m-k+1}c_i\le 10^7$ 。 | 子任务编号 | $n\le $ | $m \le$ |特殊性质 |分值 | | :----: | :--: | :-----: | :-----: |:-----: | | 1 | $5000$ | $5000$ | A | 10 | | 2 | $5000$ | $5000$ | B | 10 | | 3 | $5000$ | $5000$ | C | 15 | | 4 | $12$ | $5000$ | 无 | 15 | | 5 | $300$ | $300$ | 无 | 25 | | 6 | $5000$ | $5000$ | 无 | 25 | 特殊性质 A : $k=m$ 。 特殊性质 B : $k=1$ 。 特殊性质 C : $n\ge m, ~\forall ~1\le i\le m,~ a_i=i$ 。