UOJ Logo

NOI.AC

#54. inform

统计

题目描述

一场天灾过后,B 市的所有主干道路都被切断了。

灾后重建的一项重要任务是恢复通信。B 市共有 $n$ 个关键的据点,而我们现在有一条关键的消息,需要所有的据点都要收到。

消息的传递有两种方式:

  • 空降:可以直接将消息传给某个据点,每次需要的代价为 $v$。
  • 通信员:可以将消息从一个据点传到另一个据点,需要的代价为两个据点在地图上的欧氏距离的平方。保证所有点的坐标均为整数,所以这个代价也一定是整数。

注意,通信员只能从已有消息的据点传递消息到另一个据点。所以,至少第一个收到消息的据点一定是通过空降的。

在保证所有的据点都收到消息的前提下,最小的总代价是多少?

输入格式

从标准输入读入数据。

输入的第一行包含空格隔开的两个数 $n, v$。

接下来 $n$ 行,每行有两个空格隔开的数 $x, y$,表示每个据点在地图上的坐标。

输出格式

输出到标准输出。

输出一行,仅包含一个整数,表示最小的总代价。

样例

输入

6 1000
0 0
0 10
20 20
30 30
80 100
100 100

输出

3200

解释

一种可能的方案如下:

  • 空降:(0, 10),代价1000
  • 通信员:(0, 10)到(0, 0),代价100
  • 通信员:(0, 10)到(20, 20),代价500
  • 通信员:(20, 20)到(30, 30),代价200
  • 空降:(100, 100),代价1000
  • 通信员:(100, 100)到(80, 100),代价400

各测试点数据规模与约定

所有测试点的 $n$ 分别为:1, 5, 9, 13, 17, 50, 300, 1000, 3000, 5000。

对于所有数据,保证 $0 \leq v \leq 100,000, 0 \leq x, y \leq 30,000$。