#1246. 月饼分割

月饼分割

image

题目背景

快乐的中秋节到啦!Dw送给了小核桃一大箱月饼!

题目描述

箱子里有 nn 块月饼,由于Dw送的是MC牌月饼,所以月饼大小和数量都不一样!每块月饼都有一个重量 vv ,以 1 为重量单位,还有一个美味值 mm ,每一个重量单位都会有 mmii 点美味值,小核桃想要在吃到的每块月饼美味值尽量大于等于自己的胃口值 ss 的情况下吃尽量多的月饼,但总重量 vvii 不能超过自己的胃大小 tt。请你帮小核桃想想,照这种情况,他吃到的月饼最大美味值总和是多少吗?(美味值一定要尽量大于胃口值,如果没有任何月饼的美味值大于等于胃口值,小核桃就会选择不吃,美味值总和为0,如果至少有一个大于等于胃口值,那么后面如果不大于也可以吃,只要总和尽量大就行)

输入格式

第一行一个正整数 nn ,表示月饼个数 第二行两个正整数 s,ts,t ,表示小核桃的胃口值和胃大小 接下来 nn 行,每行两个整数,分别表示当前月饼的重量和美味值

输出格式

只有一个整数,表示美味值总和

3
2 6
3 1
2 2
1 4
11

数据范围

每组数据点 10 分,共 10 组数据。

数据点编号 n,s,t的范围 月饼数值范围
1~5 1n10s,t101\le n\le 10\le s,t\le 10 1vi,mi91 \le v_i,m_i \le 9
6~8 1n10s,t1021\le n\le 10\le s,t\le 10^2 1vi,mi1031 \le v_i,m_i \le 10^3
9~10 1n10s,t1031\le n\le 10\le s,t\le 10^3 1vi,mi10321 \le v_i,m_i \le 10^3*2