16002 - 老鹰捉小鸡（catch）

同学们和老师们进行了紧张刺激的老鹰捉小鸡游戏，其中同学们拍成一列作为小鸡，老师作为小鹰，已知小鸡可以划分为若干“集团”。由于小鸡集团具有很强的凝聚力，所以抓取一个小鸡获取的分数等同于包含其的同“集团”最长子段中所具有的小鸡数量，一个小鸡被抓住后前后的小鸡会变成相邻的小鸡。由于小鸡们个人的实力都差不多，因此抓取一只小鸡的代价相等，请你得出抓取k个小鸡能获取的最高分数

始时给出一个长度为n的序列，表示初始情况下形成“集团”的情况（只有在初始情况下我们把形成的相同“集团”的子段也称之为“集团”），并且给出其所属类别。以及一个整数k表示老鹰最多能抓取的小鸡数。

输出能获得的最高分数ans，题目数据保证k<=n，如果得到多个最高分数，只需输出其中一个

从文件catch.in中读入数据

输入的第一行包含2个整数，分别为n,k，n表示形成小鸡的“集团”数量，k表示能够抓取的最大小鸡数目

接下来的两行都包含n个整数，分别表示从左到右的第i个“集团”的类别C_i，每个“集团”中包含的小鸡数目{Num}_i

输出文件到catch.in。输出仅一个数字，表示能获得的最高分数。

样例可以用下图来表示，其中1代表绿色小鸡，2代表黄色小鸡

如果在第3个“集团”中抓住三只小鸡，会变成如下的局面

我们可以通过在第2个和第4个“集团”中各抓取两个小鸡，获得5+4+5+4=18 分，注意有一种看似是最优解的方法是在第3个“集团”抓取3个小鸡，并从2和4合并的“集团”中抓取一个小鸡，但此时只能获得3+2+1+10=16分

对于100%的数据点${Num}i\le100,k\le\sum{i=1}^{n}{Num}_i$

入门教程