#BPV02. 闭幕前的节目单
闭幕前的节目单
闭幕前的节目单
机器人表演队要在总时长不超过 T 分钟的活动中安排节目。活动最后必须预留 L 分钟进行闭幕仪式,这部分时间不能用于表演,也不产生节目得分。
队伍会表演 N 种小节目。第 i 种小节目每次占用 t_i 分钟,产生 p_i 点欢乐值。机器人可以反复表演同一种小节目,每次的用时和欢乐值相同;节目之间没有额外的准备时间。
所有节目都必须完整表演,闭幕前可以空闲,也可以不安排任何节目。求最多能产生多少点欢乐值。
输入格式
第一行三个整数 N、T、L。
接下来 N 行,每行两个整数 t_i、p_i。
输出格式
输出一个整数,表示题目所求的最大值。
数据范围
1 ≤ N ≤ 100,1 ≤ T ≤ 1000,0 ≤ L ≤ T;1 ≤ t_i ≤ 1000,1 ≤ p_i ≤ 10000。
样例
输入
3 15 3
5 8
3 4
8 13
输出
17
说明
预留闭幕后,可表演 12 分钟。选择第 3 种和第 2 种节目各一次,共用 11 分钟,获得 13+4=17 点欢乐值;这是最优值。