All submissions for this problem are available.$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.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.