All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Roy and Flower Farm
/

Algorithms, Dynamic Programming, Two dimensional

Problem
Editorial
Analytics

Roy is the owner of a flower plant farm and sells flower plants for a living.
Now the problem with flower plants is that they wither in a night if not taken care of. So at the end of the day, to make flower plants wither-resistant Roy uses special fertilizers.

There are N number of plants not sold on one particular day (say today), but Roy can sell them the next day (say tomorrow) if he fertilizes them tonight.
Roy sells a flower plant for Rs. X. Cost of fertilizing a plant is Rs. Y.
Currently Roy has P Rupees with him.

Given the selling price X and fertilizing cost Y of N plants, your task is to find minimum amount A (AP) that he should spend in fertilizing plants such that the total money he has after selling plants on the next day is maximized. Assume that all the fertilized plants are sold on the next day.

Input Format:
First line contains integer T - number of test cases.
Second line contains two space separated integers N and P.
Following N lines each contain two space separated integers X and Y.

Output Format:
Print the two space separated integers A and B in a new line for each test case.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 100
1 ≤ X,Y ≤ 1000
1 ≤ P ≤ 10000

SAMPLE INPUT
2
2 50
80 40
60 20
5 100
100 40
50 40
40 50
60 20
100 50
SAMPLE OUTPUT
20 90
90 210
Explanation

Test Case #1:
He has Rs. 50 with him in the beginning. To fertilize both the plants he needs Rs. 60. So he has to choose one of them. Now profit from both the plants is equal i.e Rs. 40. But the cost of fertilizing second plant is less. Hence the Minimum Amount to spend is Rs. 20 and total money he has after selling the plants is 50 - 20 + 60 = 90

Test Case #2: Profit for each of the plants is 60, 10, -10, 40, 50 respectively. He has Rs. 100 with him. The optimal selection would be fertilize first and last plant. So Minimum Amount to spend is Rs. 90 and total money he has after selling the plants is 100 - 40 - 50 + 100 + 100 =210

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?