题目内容

某训练步按顺序处理 $n$ 个样本，要把它们切成若干个微批次，使总耗时最小。第 $i$ 个样本有显存占用 $m_i$、计算耗时 $t_i$ 和有符号损失 $g_i$。

每个微批次是一段下标连续的样本 $[L, R]$（$1 \le L \le R \le n$）。切分覆盖每个样本恰好一次，各段从左到右相接，第一段从 $1$ 开始，最后一段到 $n$ 结束。

处理规则

一、合法区间

区间 $[L, R]$ 同时满足下面两条才合法：

• $R - L + 1 \le K$
• $m_L + m_{L+1} + \cdots + m_R \le M$

存在某个 $m_i > M$ 时，没有合法切分。否则每个单样本区间都合法。

二、耗时

合法区间 $[L, R]$ 的耗时为

$T(L, R) = (R - L + 1) \times \max(t_L, t_{L+1}, \ldots, t_R) + \left| g_L + g_{L+1} + \cdots + g_R \right|$

一种切分的总耗时等于其中每个微批次的 $T$ 之和。结果是合法切分里的最小总耗时。没有合法切分时，结果为 $-1$。

输入描述

第一行三个整数 $n$、$K$、$M$，相邻整数之间用空格分隔。

第二行 $n$ 个整数 $m_1, m_2, \ldots, m_n$，相邻整数之间用空格分隔。

第三行 $n$ 个整数 $t_1, t_2, \ldots, t_n$，相邻整数之间用空格分隔。

第四行 $n$ 个整数 $g_1, g_2, \ldots, g_n$，相邻整数之间用空格分隔。

约束

• $1 \le n \le 2000$
• $1 \le K \le n$
• $1 \le M \le 10^9$
• $1 \le m_i \le 10^9$
• $1 \le t_i \le 10^6$
• $-10^6 \le g_i \le 10^6$

最小总耗时在 $64$ 位有符号整数范围内。

输出描述

输出一行一个整数，表示最小总耗时。没有合法切分时，输出 $-1$。

样例1

输入

3 3 9
2 2 2
1 1 1
4 -6 4

输出

5

说明

整段 $[1, 3]$：样本数是 $3$，显存之和是 $6$，两条都满足。$\max(t_1, t_2, t_3) = 1$，损失之和是 $4 + (-6) + 4 = 2$，$T(1, 3) = 3 \times 1 + \left| 2 \right| = 5$。

三个单样本：$T(1, 1) = 5$，$T(2, 2) = 7$，$T(3, 3) = 5$，总和是 $17$。

$[1, 2]$ 与 $[3, 3]$：$T(1, 2) = 2 \times 1 + \left| 4 + (-6) \right| = 4$，再加上 $5$，总和是 $9$。$[1, 1]$ 与 $[2, 3]$ 的总和也是 $9$。最小总耗时是 $5$。

样例2

输入

4 2 5
3 1 1 3
2 2 9 2
0 7 -7 0

输出

22

说明

$K = 2$，长度大于 $2$ 的区间都不合法。$[1, 4]$ 的显存之和是 $8$，大于 $M$。长度不超过 $2$ 的区间显存之和都不超过 $4$，全部合法。

五种合法切分的总耗时：

• 四段单样本：$T(1, 1) = 2$，$T(2, 2) = 9$，$T(3, 3) = 16$，$T(4, 4) = 2$，总和 $29$。
• $[1, 2]$、$[3, 3]$、$[4, 4]$：$T(1, 2) = 2 \times 2 + \left| 7 \right| = 11$，总和 $11 + 16 + 2 = 29$。
• $[1, 2]$、$[3, 4]$：$T(3, 4) = 2 \times 9 + \left| -7 \right| = 25$，总和 $11 + 25 = 36$。
• $[1, 1]$、$[2, 3]$、$[4, 4]$：$T(2, 3) = 2 \times 9 + \left| 7 + (-7) \right| = 18$，总和 $2 + 18 + 2 = 22$。
• $[1, 1]$、$[2, 2]$、$[3, 4]$：总和 $2 + 9 + 25 = 36$。

最小总耗时是 $22$。