All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Chandu and his toy stack
Tag(s):

Data Structures, Greedy Algorithms

Problem
Editorial
Analytics

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.

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 \(i\;th\) stack and final height of \(i\;th\) 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:

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

SAMPLE INPUT
1
3 6 4
3 1
1 2
1 2
SAMPLE OUTPUT
10
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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?