Under construction

Still being built. Things may change

Galactic Confederation

Time limit2sMemory limit512 MB

Summary
Given M planes and N planet positions, count how many planets fall in the most populated region formed by the planes.
Level

Medium4 of 10

Topics
Geometry, Hash map, Brute force, Implementation
Solved
No attempts yet

Problem

The Galactic Confederation reorganized its administration to spread the resources of its fleet more evenly. It started by cutting all of space into regions. A set of infinite planes was fixed first, and every piece those planes cut space into is one region. Some regions are unbounded, and bounded regions can appear too.

The planes were chosen so that no plane meets the orbit of any planet. Each planet therefore stays inside a single region for its whole orbit. A planet inside a region never crosses a plane into another region.

Given the equations of the planes and the positions of the planets, find how many planets lie in the region that holds the most planets.

Input

The first line has two integers MM and NN, the number of planes and the number of planets. (1≤M≤5001 \le M \le 500, 1≤N≤100001 \le N \le 10000)

Each of the next MM lines has four integers AA, BB, CC, DD, the coefficients and the constant term of the equation Ax+By+Cz=DAx + By + Cz = D of one plane. (−10000≤A,B,C,D≤10000-10000 \le A, B, C, D \le 10000)

Each of the following NN lines has three integers XX, YY, ZZ, the position (X,Y,Z)(X, Y, Z) of one planet. (−10000≤X,Y,Z≤10000-10000 \le X, Y, Z \le 10000)

Output

Print one line with a single integer, the number of planets in the region that contains the most planets.

Examples2

  1. Example 1

    Input
    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
    
    Expected output
    3
    
  2. Example 2

    Input
    4 8
    0 0 1 1
    1 0 1 2
    -1 1 1 3
    -1 -1 1 3
    0 0 5
    0 0 4
    0 0 -2
    1 0 5
    40 19 104
    13 26 84
    89 -45 18
    3 1 0
    
    Expected output
    5