Problem 3473. -- 面包

3473: 面包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

Farmer John有N(1≤N≤100)种不同类型的面包(编号1~N),每种面包的数量无限多。Farmer John想用这些面包堆
成一个高度不超过T   ( 1 ≤ T ≤1000 )的面包塔。第i种面包的价值是 v_i(1≤v_i≤1000000),高度是H_i (5≤
H_i≤T),而且高度是5的倍数。己知一个常量K(1≤K≤T),如果某块面包的高度≥K,我们称它为"大面包",大面包会
把堆在它下面的所有面包都压扁(即使下面同样有大面包)。面包被压扁后价值不会改变,但高度变成了原来的4/5
。由于所有面包原来高度都是5的倍数,所以压扁后的高度还是整数。某块面包被压扁一次后不会再被压扁第二次
,也就是说每块面包要么被压扁要么不被压扁。现在的问题是:Farmer John堆成一个高度不超过T(1≤T≤1000)的
面包塔,能获得最大的价值是多少?例如:T=53, K=25。以下有三种不同类型的面包,数量无限:
Type Value Height
1 100 25
2 20 5
3 40 10
FJ能够堆出下面的面包塔:
Type Height Value
top-> [1] 25 100
  [2] 4 20   <-被第[1]块面包压扁了
  [3] 8 40   <-被第[1]块面包压扁了
  [3] 8 40   <-被第[1]块面包压扁了
bottom-> [3] 8 40  <-被第[1]块面包压扁了
由于最上层的面包高度是25≥K,所以把它下面所有的面包压扁,面包塔总高度是:25+4+8+8+8=53,刚好不超过T,
所以是合法的,面包塔的总价值是:100+20+40+40+40=240。这也是最优方案了。

Input

第1行:三个整数:N, T, K。
第2~N+1行;第i+1行有两个整数:V_i、H_i,表示第i种面包的信息。

Output

一行:能堆出来的最大价值。

Sample Input

3 53 25
100 25
20 5
40 10

Sample Output

240

HINT

Source

[Submit][Status]