Valentine day special
All submissions for this problem are available.
It is Valentine's day. Sankar went to a theme park to enjoy the day with his girl friend. There are 'N' couple rides in the theme park. Sankar's budget for spending is 'M' rupees. Sankar is a clever guy. He never spends more than his budget. A ride 'i' costs 'Ci' rupees. Sankar had 'K' discount coupons which he got from his friend Sivakumar. If Sankar uses a coupon on a ride 'i', then the ride costs 'Di' rupees instead of 'Ci' rupees. But the condition to use a coupon is that "He can use atmost one coupon per ride". The more the number of rides Sankar and his girl friend take, the more their love increases. Help Sankar find the maximum number of rides he can take, provided he doesn't spend more than his budget.
Note: Same ride cant be taken again. A ride can be taken only once.
There are multiple test case files.
The first line of each test case has three space separated integers N, K and M.
Then follows N lines, each line consists two space separated integers Ci and Di, the original cost of the ith ride and the
cost of the ith ride if the coupon is used on it.
For each test case, output on a single line, the maximum number of rides they can take.
1 <= N <= 50,000
1 <= K <= N
1 <= M <= 10^14
1 <= Ci <= 10^9
1 <= Di <= Ci
Input 4 1 7 3 2 2 2 8 1 4 3 Output: 3
He has 7 rupees and only one coupon. He would use the coupon on the 3rd ride (1 based index, i.e., the ride which costs 8
1). With remaining 6 rupees, he can ride either (1st and 2nd) or (2nd and 4th). So, totally 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.