又是一年秋季时,陶陶家的苹果树结了 n 个果子。陶陶又跑去摘苹果,这次他有一个 a 公分的椅子。当他手够不着时,他会站到椅子上再试试。
这次与 NOIP 2005 普及组第一题不同的是:陶陶之前搬凳子,力气只剩下 s 了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在 s<0 之前最多能摘到多少个苹果。
现在已知 n 个苹果到地上的高度 x_i ,椅子的高度 a ,陶陶手伸直的最大长度 b ,陶陶所剩的力气 s ,陶陶摘一个苹果需要的力气 y_i ,求陶陶最多能摘到多少个苹果。
第 1 行:两个数 苹果数 n ,力气 s 。
第 2 行:两个数 椅子的高度 a ,陶陶手伸直的最大长度 b 。
第 3 行~第 3+n-1 行:每行两个数 苹果高度 x_i ,摘这个苹果需要的力气 y_i 。
只有一个整数,表示陶陶最多能摘到的苹果数。
8 15 20 130 120 3 150 2 110 7 180 1 50 8 200 0 140 3 120 2
4
对于 100\% 的数据, n\leq 5000 , a\leq 50 , b\leq 200 , s\leq 1000 , x_i\leq 280 , y_i\leq 100 。