github.com/captn3m0/codechef.git

---
{"category_name":"easy","problem_code":"DEM2019A","problem_name":"Surgical Strikes","languages_supported":{"0":"C","1":"CPP14","2":"JAVA","3":"PYTH","4":"PYTH 3.6","5":"PYPY","6":"CS2","7":"PAS fpc","8":"PAS gpc","9":"RUBY","10":"PHP","11":"GO","12":"NODEJS","13":"HASK","14":"rust","15":"SCALA","16":"swift","17":"D","18":"PERL","19":"FORT","20":"WSPC","21":"ADA","22":"CAML","23":"ICK","24":"BF","25":"ASM","26":"CLPS","27":"PRLG","28":"ICON","29":"SCM qobi","30":"PIKE","31":"ST","32":"NICE","33":"LUA","34":"BASH","35":"NEM","36":"LISP sbcl","37":"LISP clisp","38":"SCM guile","39":"JS","40":"ERL","41":"TCL","42":"kotlin","43":"PERL6","44":"TEXT","45":"SCM chicken","46":"PYP3","47":"CLOJ","48":"R","49":"COB","50":"FS"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"vishal_nnd0","problem_tester":null,"date_added":"15-04-2019","tags":{"0":"vishal_nnd0"},"time":{"view_start_date":1556307900,"submit_start_date":1556307900,"visible_start_date":1556307900,"end_date":1735669800},"is_direct_submittable":false,"layout":"problem"}
---
<span class="solution-visible-txt">All submissions for this problem are available.</span>$N$ Indian Air Force fighter planes are located in different bases across the country. Each airbase is described by some integer coordinate $(x,y)$. The Air Force plans to do surgical strikes on a maximum of $M$ different targets in enemy territory (which are also described by cartesian coordinates) and then come back to the common main airbase at coordinate $(baseX, baseY)$ .   

Each army base and the targets are recognised by a secret integer $ID$. The time taken for an aircraft to go from a base to a target is the prime factor of the Manhattan Distance between the base and the target that is just greater than the $ID$ of the source base (In case the $ID$ is greater than or equal to the largest prime factor, then consider the $ID$ itself). Similarly, the time taken for an aircraft to go from a target to the main base is the prime factor of the Manhattan Distance between the target and the main base that is just greater than the $ID$ of the target (In case the $ID$ is greater than or equal to the largest prime factor, then consider the $ID$ itself).   

Each Aircraft needs to leave the base, reach target and come back to the main base in a maximum time of $T$.  One aircraft can go to only one target before going to the main base.

Find the maximum number of targets that can be reached in the enemy territory.


###Input
- The first line contains three space separated integers $N$, $M$ and $T$ respectively.
- The next $N$ lines contain 3 integers denoting $x$ coordinate, $y$ coordinate and the $ID$ of the air bases.
- The next $M$ lines contain 3 integers denoting $x$ coordinate, $y$ coordinate and the $ID$ of the targets.
- The last line contains two integers denoting the  $baseX$ and $baseY$ coordinate.

###Output

Output a single integer which is the maximum number of targets that can be reached.

###Constraints 
- $ 1\leq N,M \leq 400$
- $ 0 \leq x, y, baseX, baseY \leq 5*10^6$
- $ 0 \leq ID \leq 5000$
- $ 0 \leq T \leq10^7$

###Sample Input

2 2 35   
1 2 15   
2 10 20   
2 1 8   
5 6 12   
5 5   

###Sample Output
2

###Sample Explanation
Aircraft from first base can go to target 1 and then to the main base in time 23 and aircraft from second base can go to target 2 and then to the main base in time 32. So 2 targets can be reached in less than time T=35.