【问题描述】

平面直角坐标系中有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