DAVIDG - Davids Greed


The King David it’s a particularly miser character. He have all the gold in his kingdom, and never lends a single coin to anyone. Years passed, and the streets in his kingdom, made by his father, King Enrique, started to deteriorate. The villagers couldn’t traffic with their carts without dropping some of their content.

This problem was affecting the merchants, because they were losing food and other stuff that they sell. So they decided to go to the castle and block the entrance, so the king couldn’t get out until he promised that he would restore the streets.

The King, tired by the annoyance of the people, decided to promess to restore the streets of his kingdom, but because he’s too greedy, he will restore only the ones that are important for the city, let’s call them “vital streets”.

The vital streets connect a commercial point A to a commercial point B in the city such that there will never exist 2 ways to go from point A to point B. This is given by some coordinates X and Y, you can assume the commercial point will be a single point in a space.

The original streets, built by King Enrique, connects every point with the other points, so point A it’s connected with point B, C, D, and so on. So restore every street would be too expensive, that’s why King David will restore only the “vital streets”, but he is not really good at this type of calculations, so he need you to write a program that help him out.

The cost of restoring a street is given by its length and some value P, that tell how much cost to restore a single unit of distance. By example, if P = 3, and the distance of points A and B it’s 3.5, then the total cost of restoring that street would be 3.5 * 3. Note: you have to round up the total cost of the street.


Input

The first line of input will consist of an integer T, denoting the number of test cases. Every test case will have by first line 2 integers, N and P, denoting the number of points and the unitary cost. Then N lines follow, every of them having 2 numbers Xi  and Yi , denoting the coordinates in the cartesian plane of every commerciant points.

Output

For each test case output a single line containing this: “Scenario #i: j”, where i is the number of the test case, starting in one, and j it’s the minimum cost of restoring the streets, such as the restored streets let the villagers to go from one point to another point. Since this number can be quite large, output j mod 10^9 + 7.

Example

Input:

2

4 1

35 46

29 13

44 0

27 17

3 18

18 0

11 17

2 31

Output:

Scenario #1: 56

Scenario #2: 631


Constraints:

1 ≤ N ≤ 1,000

-1,000 ≤ Xi , Yi ≤ 1,000

1 ≤ P ≤ 1,000


hide comments
Antonio Roberto Paoli: 2018-10-30 01:14:33

I don't know how to solve it in this time limit, but first test case is really 56. You must round up the cost of each street before sum.

Last edit: 2018-11-01 23:56:30
jayantisswani: 2017-09-28 18:55:02

Is the output of the given testcases correct?
The output for first testcase should be 54..isn't it?

Shubham Jadhav: 2017-05-05 11:22:56

My 100th :)

mateifl: 2017-01-21 12:42:24

Can be solved with Prim + priority queue in O(n^2).

kshubham02: 2017-01-16 12:04:31

I submitted a solution that was giving output 55 for the first test case, and expected WA.
To my surprise, judge showed "running(4)" status before giving WA. What does this mean? Isn't the given case the first test case of the input file? If it is, is the solution 56 here incorrect?

Edit: 55 comes by rounding up 54.4, and many people have already commented that they got 54. This strengthens the possibility that 56 shown here is incorrect.

Last edit: 2017-01-16 12:14:26
ASHUTOSH DWIVEDI: 2016-06-22 00:22:01

Problem Setter You should also provide no of test cases in problem....

ASHUTOSH DWIVEDI: 2016-06-18 18:48:19

Last edit: 2016-06-18 19:52:24
ASHUTOSH DWIVEDI: 2016-06-18 18:21:47

Last edit: 2016-06-18 19:52:35
shikhar0037: 2016-05-20 21:13:28

Getting TLE on Prims also (using priority queue) . Is there any other optimisation required ?

miloszmaki: 2016-05-04 19:59:25

Is it possible to get AC with Kruskal on all O(n^2) edges? Did anyone manage to do that?
Is it necessary to implement the 'real' EMST in O(n log n)?


Added by:Luis Arguello
Date:2012-04-22
Time limit:0.100s-0.180s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem.