Mahmud vs. Ridwan (Hard)

faiyaz26 ProgKriya Aug'15
Limits 1s, 512 MB

Mahmud is playing a game with Ridwan. Mahmud is given N cartesian points by Ridwan. Mahmud can connect two points by drawing a line. Now there is a condition, he cannot draw a line which is already parallel to previously drawn lines. For each line drawn he will earn $D. Now Mahmud wants your help to find out what will be his maximum possible earning?

Input

Input starts with an integer T (0 < T ≤ 20), denoting the number of test cases.

Each test case starts with two Integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤ 1000000000), where N denotes the number of points and D denotes the money you will earn for drawing a line. Then there will be N lines with two integers denoting the X and Y coordinates (-1000000000 ≤ Xi, Yi ≤ 1000000000). Each point will be distinct.

Output

For each test case, print the case number and Mahmud’s maximum possible earning.

Sample

InputOutput
1
4 1
-2 0
1 1
-1 1
0 0
Case 1: 4

Mahmud can draw 4 lines with slope -1, 0, 1/3, and 1.


Submit

Login to submit.

Statistics

36% Solution Ratio
fsshakkhorEarliest, Aug '15
sakib23Fastest, 0.4s
daryanZLightest, 2.2 MB
arnab_sustShortest, 586B
Toph uses cookies. By continuing you agree to our Cookie Policy.