Chandu and his toy stack

2.8

22 votes
Approved, Data Structures, Easy, Greedy Algorithms, Open
Problem

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 H1,H2...Hn (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.

Input:

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 ith stack and final height of ith stack.)

Output:

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.

Constraints:

1t100,
1N105,
1a[i],b[i]106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?