Under construction

Still being built. Things may change

Snowflake Tanghulu

Interview

Time limit2sMemory limit512 MB

Summary
Given fruit positions and candidate endpoints, find the most fruits one skewer from (0, 0) to a candidate endpoint can pierce.
Level

Medium5 of 10

Topics
Hash map, Math, Sorting, Binary search
Solved
No attempts yet

Problem

Freshmen who entered Sookmyung Women's University like cute snowflakes, so they want to make snowflake tanghulu. Snowflake-shaped fruits are placed on a two-dimensional coordinate plane. A skewer runs from (0,0)(0, 0) to an endpoint (e_x,e_y)(e\_x, e\_y) and pierces every fruit on the segment that includes that endpoint. There are MM candidate endpoint positions. Find the largest number of fruits that a single skewer can pierce, over all candidate endpoints.

Input

The first line contains the number of fruits NN and the number of candidate endpoints MM, both integers. (1≤N≤300 0001 \leq N \leq 300\,000; 1≤M≤300 0001 \leq M \leq 300\,000) The next NN lines each contain a fruit position (f_x,f_y)(f\_x, f\_y), separated by a space. (−109≤f_x,f_y≤109-10^9 \leq f\_x, f\_y \leq 10^9, both integers.) No two fruits share the same position. The next MM lines each contain a candidate endpoint (e_x,e_y)(e\_x, e\_y), separated by a space. (−109≤e_x,e_y≤109-10^9 \leq e\_x, e\_y \leq 10^9, both integers.) No two candidate endpoints are the same. No fruit or endpoint is (0,0)(0, 0). A fruit position and an endpoint may be the same point.

Output

Print the largest number of fruits that can be pierced by one skewer.

Examples1

  1. Example 1

    Input
    9 5
    -1 -1
    -1 0
    -1 1
    1 0
    1 1
    1 2
    2 2
    2 4
    3 3
    0 3
    1 1
    4 0
    4 4
    3 6
    
    Expected output
    3