Taxi Driver

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Mark is a taxi driver working in a big city. A taxi company, where Mark works, has N regular customers. The house of a regular customer can be described as a point of the Cartesian plane with nonnegative integer coordinates. Recently, Mark's boss has given him a big assignment: he should drive between each pair of regular customers to make sure all the direct roads between the customers are in a good condition. Now Mark is wondering how big the total distance he will be driving during this assignment is.
More formally, you are given a sequence p_{1}, p_{2}, ..., p_{N} of points of the Cartesian plane with nonnegative integer coordinates. These points describe the houses of the regular customers. Also, you are given two positive integer parameters a and b. The distance between points (x_{1}, y_{1}) and (x_{2}, y_{2}) is equal to max(a × x_{1}  x_{2}, b × y_{1}  y_{2}).
You task is to calculate the sum of the distances between each pair of the given points.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of the test case description contains one integer N denoting the size of the sequence. The second line contains two positive integers a and b.
Each of the next N lines contains two nonnegative integers x_{i} and y_{i} denoting the coordinates of the corresponding point of the sequence.
Output
For each test case, output a single line containing one integer: the sum of the distances between each pair of the given points.Constraints
 1 ≤ T ≤ 200000
 1 ≤ N ≤ 200000
 1 ≤ a, b ≤ 100
 0 ≤ x_{i}, y_{i} ≤ 10^{6}
 The sum of all N in the input is not greater than 200000
Example
Input: 2 4 1 1 0 0 0 1 1 0 1 1 7 6 9 1 2 2 3 4 1 5 431 213 2 32 12 11 99 Output: 6 32274
Author:  kostya_by 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/TDRIVER 
Tags  cook57, geometry, kostya_by, manhattan, mediumhard 
Date Added:  16032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions