【问题描述】
平面直角坐标系中有n个信号点。现在要建立一个基站,覆盖所有的信号点。
一个基站的覆盖范围是一个正整数d,如果一个点与基站的曼哈顿距离不超过d,那么这个点就能被覆盖。
有m个地点可以用来建立基站,第i个地点有一个费用系数vi。如果你在第i个地点建立一个覆盖范围为di的基站,那么费用是vi与di的乘积。
现在,你需要从这m个地点中选择一个地点用来建立基站,基站的覆盖范围由你决定,要求能覆盖所有信号点。
你需要找出费用最小的建立方案。
【输入格式】
第一行两个正整数n、m
接下来n行,每行两个正整数xi,yi。表示第i个信号点的坐标是(xi,yi)
接下来m行,每行三个正整数xj,yj,vj。表示第j个可以用来建立基站的地点的坐标是(xj,yj),费用系数是vj。
【输出格式】
输出一行一个数,建立基站的最小费用。
注意基站的覆盖范围虽然可以由你决定,但必须是正整数。
【样例输入】
3 2
1 5
2 3
6 1
3 3 7
3 2 9
【样例输出】
35
【样例解释】
选择(3,3),建立覆盖范围为5的基站,所有信号点到(3,3)的曼哈顿距离都不超过5,都能被覆盖。费用是5*7=35
【数据规模和约定】
对于30%的数据, n,m<=10
对于60%的数据, n,m<=1000
对于100%的数据, n,m<=100000,1<=xi,yi,xj,yj,vj<=10^9