题目内容

有一个由 $N$ 个数据交换节点组成的新型数据传输网络，节点编号依次为 $0$ 到 $N-1$。数据包从节点 $0$ 出发，必须按编号递增的顺序依次经过每一个节点，最终离开节点 $N-1$。节点 $i$ 在默认情况下处理数据包会产生 $delay[i]$ 单位的处理时延。

每个节点 $i$ 都支持一种优先转发模式。若节点 $i$ 被配置为优先转发模式，它会为数据包附加一个特殊标记。该标记的作用范围覆盖节点 $i$ 本身以及紧随其后的 $win\_size[i]$ 个节点，也就是所有满足 $i \le j \le i + win\_size[i]$ 的节点 $j$。如果 $i + win\_size[i] \ge N$，则作用范围在节点 $N-1$ 处截断。

对于任意一个被该标记覆盖的节点 $j$，其处理时延会从 $delay[j]$ 减少 $opt\_delay[i]$。若减少量超过 $delay[j]$，则节点 $j$ 的最终处理时延按 $0$ 计算。如果节点 $j$ 同时被多个配置了优先转发模式的节点覆盖，那么这些节点带来的减少量会累加，也就是节点 $j$ 的总减少量等于所有覆盖它的 $opt\_delay[i]$ 之和。

你的任务是在 $N$ 个节点中选择不超过 $K$ 个节点配置优先转发模式，使得数据包经过全部节点后产生的总处理时延尽可能小。请计算这个最小总处理时延。

约束条件：

• $N$ 的范围是 3 到 50。
• $K$ 的范围是 0 到 10。
• $delay[i]$ 和 $opt\_delay[i]$ 都是不超过 10^7 的非负整数。
• $win\_size[i]$ 是不超过 3 的非负整数。
• 所有输入数据均为整数。

输入描述

第一行包含两个整数 $N$ 和 $K$，分别表示数据交换节点的总数以及最多允许配置优先转发模式的节点数。

第二行包含 $N$ 个整数，依次表示每个节点的默认处理时延 $delay[0..N-1]$。

第三行包含 $N$ 个整数，依次表示每个节点配置优先转发模式后影响的后续节点数 $win\_size[0..N-1]$。

第四行包含 $N$ 个整数，依次表示每个节点配置优先转发模式时的时延优化值 $opt\_delay[0..N-1]$。

输出描述

输出一个整数，表示在最多选择 $K$ 个节点配置优先转发模式的情况下，数据包经过所有节点后所能得到的最小总处理时延。

样例1

输入

3 0
5 3 2
0 0 0
10 20 30

输出

10

说明

共有 3 个节点，且 $K=0$，因此不能配置任何优先转发模式。

数据包经过每个节点的时延就是默认时延，分别为 5、3、2。

总时延为 $5+3+2=10$，所以最小总时延为 10。

样例2

输入

3 1
10 10 10
2 0 0
5 100 100

输出

15

说明

当选择节点 0 配置优先转发模式时，它的覆盖范围是节点 0 到节点 0+2=2。

每个覆盖节点的时延都减少 $5$，于是三个节点的时延分别变为 $10-5=5$、$10-5=5$、$10-5=5$。

总时延为 $5+5+5=15$。

如果选择节点 1 或节点 2，它们只能覆盖自身。虽然减少量 $100$ 超过了默认时延 $10$，节点时延按 $0$ 计算，但另外两个节点仍为 $10$，总时延为 $10+0+10=20$。

因此最小总时延为 15。

样例3

输入

4 2
8 5 9 6
1 2 0 1
3 4 10 5

输出

11

说明

最优配置是选择节点 1 和节点 2。

节点 1 的覆盖范围是节点 1 到节点 3，减少量为 $4$。

节点 2 的覆盖范围是节点 2 自己，减少量为 $10$。

各节点最终时延如下：

• 节点 0 未被覆盖，时延为 $8$。
• 节点 1 只被节点 1 覆盖，时延为 $5-4=1$。
• 节点 2 同时被节点 1 和节点 2 覆盖，总减少量为 $4+10=14$，而 $9-14<0$，所以按 $0$ 计算。
• 节点 3 只被节点 1 覆盖，时延为 $6-4=2$。

总时延为 $8+1+0+2=11$，因此最小总时延为 11。