拼拼图的小杉

拼拼图的小杉

测试数据来自 system/1392

背景

小杉的幻想来到了经典日剧《死亡拼图》的场景里……
被歹徒威胁,他正在寻找拼图(-.-干嘛幻想这么郁闷的场景……)。

突然广播又响了起来,歹徒竟然又有了新的指示。

小杉身为新一代的汤浅,有责任带领大家脱离危险!

(若对情节有任何疑问,请观看原剧)

描述

歹徒告诉小杉,他正在寻找的拼图块其实可以拼成N个 有顺序的 完整的拼图。

每个完整的拼图由若干个拼图块组成。

歹徒要求小杉把拼图按拼出的顺序划分成M个集合,一个拼图集合由若干个完整的拼图组成,并且总的拼图块的数目不超过T。并且,构成集合的拼图是不能交叉的,例如,当拼图1与拼图3被放在拼图集合1中之后,拼图2就只能放进拼图集合1或者不放进任何拼图集合。

小杉要找出划分成M个集合后,M个集合中最多能有多少个完整的拼图。

格式

输入格式

每组测试数据的
第一行有三个,为N,M,T(1<=N,M,T<=1000)
第二行有N个数,按照拼出拼图的顺序给出N个拼图分别含有多少个拼图块(拼图块的个数是不超过T的正整数,并且你不必考虑在现实中是否真正存在该个数的拼图)。

特别地,对于30%的数据,有1<=N,M<=100

输出格式

对每组数据输出一行一个数字,为M个拼图集合最多包含的拼图个数

样例1

样例输入1

6 2 4
1 1 3 1 2 2

样例输出1

5

限制

每个测试点1s

提示

对于样例数据,1个可行的方案如下
拼图集合1放拼图1,2和拼图4,
拼图集合2放拼图5和拼图6
于是包含5个拼图

并且显然不存在能够放5个以上拼图的方案

来源

lolanv

信息

ID
1487
难度
(无)
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者