All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Chandu and his toy stack

Data Structures, Greedy Algorithms


After setting up the area. Chandu wanted all his toys to be stacked there in that area. So that all of them are accessible easily. Currently, He is having N stacks of toys each with height \(H_1,H_2...H_n\) (assuming all toys are of same height).Chandu did not like the configuration much and want to change the height of each stack. To increase the height of a particular stack he can add some toys to it and to decrease the height he can take out some toys from that stack. Chandu, knows that he requires X units of effort for putting up an item onto the stack and Y units of effort for removing it. Help, chandu in setting up his toys.


First Line of input contains an integer t, which is the number of test cases. then, t lines follow where first line of each test case contains three integers N, X and Y then N lines follow containing two integers each \(a[i]\) and \(b[i]\) (Initial height of \(i\;th\) stack and final height of \(i\;th\) stack.)


Output an integer which is the minimum effort required.

NOTE: he just need to make stacks of given height. Not necessarily each stack should be made from its corresponding stack.


\(1 \le t \le 100, \)
\(1 \le N \le 10^5, \)
\(1 \le a[i],b[i] \le 10^6\)

3 6 4
3 1
1 2
1 2

Here, He is having 3 stacks initially of height \(3,1\) and 1 He can take out one toy from first stack to get a stack with two toys with 4 units of effort. He can put toy on second stack to get a stack with two toys with 6 units of effort. Total effort = \(10\) units. After the two operations he will have three stacks with required heights.

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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications