[Usaco2010 Jan]Cheese Towers
时间限制：4s 空间限制：64MB
题目描述
Farmer John wants to save some blocks of his cows' delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower's height can be at most T (1 <= 1="" 2="" 3="" 4="" 5="" 10="" 20="" 25="" 40="" 53="" 100="" t="" <="1,000)." the="" cows="" have="" provided="" him="" with="" a="" virtually="" unlimited="" number="" of="" blocks="" each="" kind="" n="" (1="" different="" types="" cheese="" (conveniently="" numbered="" 1..n).="" he'd="" like="" to="" store="" (subject="" constraints="" height)="" most="" valuable="" set="" he="" possibly="" can.="" will="" sell="" rest="" support="" orphan="" calves="" association.="" block="" i-th="" type="" has="" some="" value="" v_i="" and="" height="" h_i="" (5="" which="" is="" always="" multiple 5.="" compresses.="" that="" greater="" than="" or="" equal="" k="" considered="" "large"="" crush="" any="" all="" (even="" other="" large="" ones)="" located="" below="" it="" in="" tower.="" crushed="" doesn't="" lose="" value,="" but="" its="" reduces="" just="" old="" height.="" because="" 5,="" be="" an="" integer.="" either="" not="" crushed;="" having="" above="" does="" more.="" only="" tall="" blocks;="" aggregate="" tower="" affect="" whether="" not.="" what="" total="" best="" fj="" can="" construct?="" consider,="" for="" example,="" whose="" maximum="" build="" from="" three="" blocks.="" are="" those="" 25.="" chart="" values="" heights="" various="" stacks:="" constructs="" following="" tower:="" top="" -=""> [1] 25 100 [2] 4 20 <- 8="" 40="" crushed="" by="" [1]="" above="" [3]="" <-="" bottom="" -=""> [3] 8 40 <- 4="" 8="" 20="" 25="" 40="" 53="" 100="" crushed="" by="" [1]="" above="" the="" topmost="" cheese="" block="" is="" so="" large="" that="" blocks="" below="" it="" are="" crushed.="" total="" height="" is:="" +="" does="" not="" exceed="" and="" thus="" 'legal'.="" value="" this="" best="" tower="" for="" particular="" set="" of="" blocks.="" john要建一个奶酪塔，高度最大为t。他有n块奶酪。第i块高度为hi（一定是5的倍数），价值为vi。一块高度="">=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（多块只算一次），它的高度就会变成原来的4/5.。。 很显然John想让他的奶酪他价值和最大。。 求这个最大值。。
输入格式
第一行分别是 N T K 接下来N行分别是 Vi Hi
输出格式
一行最大值
样例输入
3 53 25 100 25 20 5 40 10
样例输出
240
提示
没有写明提示
题目来源
Silver