#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 点欢乐值;这是最优值。