# 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. Constructive uDebug

### Submit 