#序列dp > [!quote] 题目背景 > > 又到了冬天了呢，渴鹅村到处大雪纷飞，好渴鹅家旁边的那一片平时波光粼粼的湖现已冻结成冰。为了防止好渴鹅由于吃不到新鲜的鱼鱼而死掉（其实大海的旁边也可以钓鱼），美公鸡就出来帮好渴鹅钓鱼。 ## 题目描述 虽然题目是鹅太公钓鱼，但是由于好渴鹅太懒了，因此好渴鹅用了一点点钞能力来让美公鸡帮他钓鱼。 现在有 $n$ 只可爱的好鱼鱼可以给美公鸡打捞，但是由于美公鸡并不懂什么鱼鱼更美味，因此在美公鸡眼中第 $i$ 只鱼鱼有 $a_i$ 的美味值，而好渴鹅是专业的（只不过比较懒），因此在好渴鹅的眼里第 $i$ 只鱼鱼的美味值为 $b_i$。 好渴鹅给了美公鸡一张长度为 $k$ 的渔网袜，这意味着美公鸡每一次撒网都可以捕捉到连续的 $k$ 条鱼鱼（鱼鱼捕完之后就没有了）。但是美公鸡由于平时“学习”过于刻苦，因此他剩余的力气就只够他撒下 $m$ 次网。美公鸡会按照他认为最优的方案进行撒网，然后拿到好渴鹅那里，然后以好渴鹅的标准计算答案。（好渴鹅的标准计算出来的答案不一定是最优的） 如果你没能输出正确的答案，那么他就会把你卖到太平洋的一个孤岛上去喝核废水。 ## 输入格式 - 第一行：三个正整数 $n,m,k$； - 第二行：共 $n$ 个整数，第 $i$ 个整数为 $a_i$； - 第三行：共 $n$ 个整数，第 $i$ 个整数为 $b_i$。 ## 输出格式 - 一行一个答案。 ## 提示说明 - $1\le m\times k\le n\le 10^3$； - $1\le m\le 10^3$； - $1\le a_i,b_i\le 10^9$。 **样例解释**：在美公鸡眼中，选择 $(4,5),(1,9),(1,9)$ 这三组是最优的，而带入到好渴鹅的眼中，答案为 $16$（选择 $(1,9),(0,1),(1,4)$）。