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

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

输出能获得的最高分数ans，如果得到多个最高分数，只需输出其中一个

**注意该题目有两条extra数据，$ k \le 200$其他保持不变**

从文件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\leq 100,k \leq$

$\sum^n_{i=1} Num_i$