时间限制： 1.5 秒

空间限制： 512 MB

题目描述

给定二维平面上 $n$ 个节点，以及 $m$ 个通讯基站。第 $i$ 个基站可以覆盖以坐标 $(x_i, y_i)$ 为中心，$2r_i$ 为边长的正方形区域，并使正方形区域内（包含边界）所有节点以 $t_i$ 单位时间的延迟进行相互通讯。

求节点 $1$ 到 $n$ 的最短通讯延迟。

输入格式

从标准输入读入数据。

第一行包含空格分隔的两个正整数 $n,m$；

接下来 $n$ 行，每行两个整数 $x_i,y_i$，代表第 $i$ 个节点的坐标；

接下来 $m$ 行，每行四个整数 $x_j, y_j, r_j, t_j$，代表第 $j$ 个通讯基站的坐标，通讯半径与通讯延迟。

输出格式

输出到标准输出。

输出一行，即节点 $1$ 到 $n$ 的最短通讯延迟；如果无法通讯，则输出 Nan。

5 5
0 0
2 4
4 0
5 3
5 5
1 2 2 5
3 5 2 6
2 0 2 1
4 2 2 3
5 4 1 2

6

样例 1 解释

$1$ 号通讯基站延迟为 $5$，覆盖节点 $1,2$；

$2$ 号通讯基站延迟为 $6$，覆盖节点 $2,4,5$；

$3$ 号通讯基站延迟为 $1$，覆盖节点 $1,3$；

$4$ 号通讯基站延迟为 $3$，覆盖节点 $2,3,4$；

$5$ 号通讯基站延迟为 $2$，覆盖节点 $4,5$。

最短延迟方案为：

1. 节点 $1$ 通过 $3$ 号基站传讯至节点 $3$，延迟 $1$；
2. 节点 $3$ 通过 $4$ 号基站传讯至节点 $4$，延迟 $3$；
3. 节点 $4$ 通过 $5$ 号基站传讯至节点 $5$，延迟 $2$；

总计延迟为 $6$。

子任务

$30\%$ 的测试数据满足 $n, m \le 100$；

对于额外 $30\%$ 的测试数据，每个通讯基站至多覆盖 $20$ 个节点；

全部的测试数据满足：

• $n, m \le 5000$；
• $0 \le x_i, y_i, r_i \le 10^{9}$；
• $1 \le t_i \le 10^5$。