# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Mahmud vs. Ridwan (Hard)

By faiyaz26 · 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.

### Statistics

36% Solution Ratio

fsshakkhorEarliest, Aug '15

sakib23Fastest, 0.4s

daryanZLightest, 2.2 MB

arnab_sustShortest, 586B