题目内容

有一个由 $N$ 个数据交换节点（编号为 $0$ 到 $N-1$）组成的新型数据传输网络。数据包从头节点 $0$ 发送，按照编号顺序依次经过每个节点 $i$ 的处理，最终到达尾节点 $N-1$。在每个节点 $i$ 处理时，会产生 $delay[i]$ 单位的处理时延。

每个数据交换节点 $i$ 支持配置优先转发模式，它将会在数据包中添加特殊的标记，使数据包在本节点和后续 $win\_size[i]$ 个节点处理时走优先转发通道，降低处理时延（$win\_size[i]$ 不包含本节点，若 $i + win\_size[i] \ge N$，则只有 $i \sim N-1$ 节点受影响）。受该标记影响的节点 $j$ 所产生的处理时延将不再是 $delay[j]$，而是 $delay[j] - opt\_delay[i]$（$opt\_delay[i]$ 为时延优化值，若 $opt\_delay[i] > delay[j]$，则节点 $j$ 产生的处理时延为 $0$）。如果某个节点被前面多个节点的优先转发模式影响，它的处理时延会被减少多次。

你的目标是在整个网络中最多选择 $K$ 个节点配置优先转发模式，使数据包达尾节点 $N$ 时，产生的总处理时延最小，输出最小的总处理时延。

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms
内存限制：C/C++ 256MB，其他语言：512MB

输入

第一行：两个整数 $N, K$，其中 $N$ 是整个网络的数据交换节点数，$K$ 是最多可以配置优先转发模式的数据交换节点数。
第二行：$N$ 个整数，表示每个节点默认情况下产生的处理时延 $delay[0..N-1]$。
第三行：$N$ 个整数，表示如果在第 $i$ 个节点配置优先转发模式，其影响的后续节点数 $win\_size[0..N-1]$。
第四行：$N$ 个整数，表示如果在第 $i$ 个节点配置优先转发模式，其时延优化值 $opt\_delay[0..N-1]$。

• $3 \le N \le 50$
• $0 \le K \le 10$
• $0 \le delay[i] \le 10^7$
• $0 \le win\_size[0..N-1] \le 3$
• $0 \le opt\_delay[i] \le 10^7$
• 所有输入数据均为整数。

输出

一个整数，表示通过配置后所能得到的最小的总处理时延。

样例1

输入：

3 1
50 40 30
3 0 1
0 50 10

输出：

80

解释：

• 若在节点 $0$ 配置，由于其时延优化值为 $0$，无任何收益，总处理时延为 $50 + 40 + 30 = 120$。
• 若在节点 $1$ 配置，其作用范围为自身节点，节点 $1$ 的处理时延从 $40$ 变为 $0$（$40 - 50 < 0$），总处理时延为 $50 + 0 + 30 = 80$，此选择最优。
• 若在节点 $2$ 配置，虽然其作用范围为 $1$，但由于无后续节点，因此只有自身节点有收益，处理时延从 $30$ 变为 $20$（$30 - 10 = 20$），总处理时延为 $50 + 40 + 20 = 110$。

样例2

输入：

5 2
10 20 30 40 50
1 0 1 3 2
15 20 0 30 35

输出：

65

解释：

• 若在节点 $0$ 和节点 $1$ 配置优先转发模式，节点 $0$ 处理时延从 $10$ 变为 $0$（$10 - 15 < 0$），节点 $1$ 会被优先转发模式影响 $2$ 次，处理时延从 $20$ 变为 $0$（$20 - 15 - 20 < 0$）。总处理时延为 $0 + 0 + 30 + 40 + 50 = 120$。
• 若在节点 $0$ 和节点 $2$ 配置优先转发模式，节点 $0$ 处理时延从 $10$ 变为 $0$（$10 - 15 < 0$），节点 $1$ 处理时延从 $20$ 变为 $5$（$20 - 15 = 5$），其余节点无变化。总处理时延为 $0 + 5 + 30 + 40 + 50 = 125$。
• 若在节点 $0$ 和节点 $3$ 配置优先转发模式，节点 $0$ 处理时延从 $10$ 变为 $0$（$10 - 15 < 0$），节点 $1$ 处理时延从 $20$ 变为 $5$（$20 - 15 = 5$），节点 $3$ 处理时延从 $40$ 变为 $10$（$40 - 30 = 10$），节点 $4$ 处理时延从 $50$ 变为 $20$（$50 - 30 = 20$）。总处理时延为 $0 + 5 + 30 + 10 + 20 = 65$，此组合最优。
• 其余组合类似：
  • 若在节点 $0$ 和节点 $4$ 配置优先转发模式，总处理时延为 $0 + 5 + 30 + 40 + 15 = 90$。
  • 若在节点 $1$ 和节点 $2$ 配置优先转发模式，总处理时延为 $10 + 0 + 30 + 40 + 50 = 130$。
  • 若在节点 $1$ 和节点 $3$ 配置优先转发模式，总处理时延为 $10 + 0 + 30 + 10 + 20 = 70$。
  • 若在节点 $1$ 和节点 $4$ 配置优先转发模式，总处理时延为 $10 + 0 + 30 + 40 + 15 = 95$。
  • 若在节点 $2$ 和节点 $3$ 配置优先转发模式，总处理时延为 $10 + 20 + 30 + 10 + 20 = 90$。
  • 若在节点 $2$ 和节点 $4$ 配置优先转发模式，总处理时延为 $10 + 20 + 30 + 40 + 15 = 115$。
  • 若在节点 $3$ 和节点 $4$ 配置优先转发模式，总处理时延为 $10 + 20 + 30 + 10 + 0 = 70$。