Problem: <image>

After William is done with work for the day, he enjoys playing his favorite video game.

The game happens in a 2D world, starting at turn 0. William can pick any cell in the game world and spawn in it. Then, each turn, William may remain at his current location or move from the current location (x, y) to one of the following locations: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

To accelerate movement the game has n fast travel towers. i-th tower is located at location (xa_i, ya_i). To be able to instantly travel to the tower from any location in the game world it must first be activated. Activation of tower i happens at the moment when the player is in cell (xa_i, ya_i) after this the tower remains active throughout the entire game.

William also knows that the game has m quests. i-th quest can be completed instantly by being at location (xb_i, yb_i) on turn t_i.

William wants to find out the maximal number of quests he will be able to complete by optimally traversing the game world.

Input

The first line contains two integers n and m (0 ≤ n ≤ 14, 1 ≤ m ≤ 100), which are the number of towers and the number of quests, respectively.

Each of the next n lines contains two integers xa_i, ya_i (1 ≤ xa_i, ya_i ≤ 10^6), which are the coordinates of fast travel towers.

Each of the next m lines contains two integers xb_i, yb_i and t_i (1 ≤ xb_i, yb_i ≤ 10^6, 1 ≤ t_i ≤ 10^9), which are the coordinates of quests and the turn at which it may be completed.

It is guaranteed that all locations in a test are different.

Output

Print a single number — the maximal number of quests William will be able to complete.

Example

Input


3 4
1 1
2 3
5 2
2 2 12
5 1 4
6 2 11
3 5 10


Output


3

Note

In the first sample test one of the possible sequences of William's actions is as follows: 

  * Spawn at (3, 2) 
  * On turn 1 move to (4, 2) 
  * On turn 2 move to (5, 2). By visiting this cell William activates tower number 3. 
  * On turn 3 move to (5, 1), where he waits for 1 turn to complete the 2nd quest 
  * On turn 5 move to (5, 2) 
  * On turn 6 move to (5, 3) 
  * On turn 7 move to (5, 4) 
  * On turn 8 move to (5, 5) 
  * On turn 9 move to (4, 5) 
  * On turn 10 move to (3, 5). By moving to this location William will complete the 4th quest 
  * On turn 10 instantly move to an already activated fast travel tower at (5, 2) 
  * On turn 11 move to (6, 2). By moving to this location William will complete the 3rd quest 
  * William will not be able to complete the quest number 1, because the tower at (2, 3) was not activated 

Solution (in CPP):

Solution:
#ifndef LOCAL
#pragma GCC optimize ("-Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

template<class t>
void print(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t,class u>
void print(const pair<t,u>&p,int suc=1){
	print(p.a,2);
	print(p.b,suc);
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

const int nmax=14;
const int mmax=105;
int mintime[1<<nmax][mmax];
int maxval[1<<nmax][mmax];
int cost[1<<nmax][nmax];
int cost2[1<<nmax][mmax];

int dist(pi a,pi b){
	return abs(a.a-b.a)+abs(a.b-b.b);
}

void slv(){
	int n,m;cin>>n>>m;
	rep(i,1<<n)rep(j,m+1){
		mintime[i][j]=inf;
		maxval[i][j]=-inf;
	}
	mintime[0][0]=-inf;
	priority_queue<pi,vc<pi>,greater<pi>> pq;
	int ans=0;
	auto reach=[&](int bit,int cnt,int t){
		chmax(ans,cnt);
		if(chmin(mintime[bit][cnt],t)){
			pq.emplace(t,bit*mmax+cnt);
		}
	};
	vc<pi> xy;
	rep(i,n){
		int x,y;cin>>x>>y;
		xy.eb(x,y);
	}
	rng(bit,1,1<<n){
		rep(to,n){
			if(bit&1<<to){
				//do nothing
			}else{
				cost[bit][to]=inf;
				rep(from,n)if(bit&1<<from)chmin(cost[bit][to],dist(xy[from],xy[to]));
			}
		}
	}
	rep(i,n)reach(1<<i,0,0);
	vc<pi> ps;
	vi ts;
	rep(i,m){
		int x,y,t;cin>>x>>y>>t;
		ps.eb(x,y);
		pq.emplace(t,i-m);
		ts.pb(t);
	}
	rng(bit,1,1<<n){
		rep(to,m){
			cost2[bit][to]=inf;
			rep(from,n)if(bit&1<<from)chmin(cost2[bit][to],dist(xy[from],ps[to]));
		}
	}
	while(si(pq)){
		auto [t,tmp]=pq.top();pq.pop();
		if(tmp>=0){
			int bit=tmp/mmax,cnt=tmp%mmax;
			dmp2(t,bit,cnt);
			if(mintime[bit][cnt]==t){
				rep(to,n)if(!(bit&1<<to))reach(bit|1<<to,cnt,t+cost[bit][to]);
			}
		}else{
			int tar=tmp+m;
			dmp2(t,tar);
			rep(bit,1<<n){
				dmp(bit);
				dmp(vi(mintime[bit],mintime[bit]+m+1));
				int u=upper_bound(mintime[bit],mintime[bit]+m+1,t-cost2[bit][tar])-mintime[bit];
				chmax(u,maxval[bit][tar]);
				if(u>0){
					dmp(u);
					chmax(ans,u);
					if(bit)reach(bit,u,t);
					rep(to,n)if(!(bit&1<<to)){
						reach(bit|1<<to,u,t+dist(xy[to],ps[tar]));
					}
					rep(to,m)if(to!=tar&&t+dist(ps[tar],ps[to])<=ts[to])
						chmax(maxval[bit][to],u+1);
				}
			}
		}
	}
	print(ans);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	//int t;cin>>t;rep(_,t)
	slv();
}