URI Online Judge | 1710


By Vinícius "Cabessa" Fernandes dos Santos BR Brazil

Timelimit: 1

The Galactic Confederation is planning an administrative reform, to better manage its resources. For that, the Confederation divided the whole space into regions. To define the regions, initially a set of planes was specified, and the regions were defined by the cuts these planes made in the space. Notice that some regions are unlimited, but there may be limited regions. The set of planes was chosen so that no plane intercepts the orbit of a planet, and therefore each planet moves within only one region during its orbit (that is, a planet inside a region will never cross a plane to another region).

Your task is to determine, given the equations of the planes and the positions of the planets, how many planets exist within the region with the largest number of planets (in other words, what is the maximum number of planets inside any region).


The input contains several test cases. The first line of a test case contains two integers M (1M500) and N (1N10000), indicating respectively the number of planes and the number of planets. Each of the M following lines contains four integers A, B, C and D (−10000A, B, C, D10000), the coefficients and the free term of the equation Ax + By + Cz = D which defines each plane. Each of the following N lines contains three integers X, Y and Z (−10000X, Y, Z10000), representingthe position (X, Y, Z) of a planet.


For each test case in the input your program must produce a single line containing a single integer, the number of planets in the region which contains the largest number of planets.

Sample Input Sample Output

2 5

1 0 0 1

2 0 0 8

0 1 0

2 2 2

3 3 3

5 5 5

2 18 4