This page is still under construction.

Parts of this page are still being built. What you see may change.

The Winds of War

Time limit2sMemory limit512 MB

Summary
Choose a convex net containing the origin that covers as many enemy units as possible while covering as few friendly ones, and report the maximum difference.
Level

Hard8 of 10

Topics
Geometry, Sorting, Dynamic programming, Brute force
Solved
No attempts yet

Problem

Colonel Trapp is trapped. After days of fighting General Position on a plateau, his mobile command unit is stuck at (0,0)(0, 0), on the edge of a cliff. But the winds are changing, and the Colonel has a secret weapon: the "epsilon net." As the Colonel's chief optimization officer, your job is to determine the maximum advantage the net can yield.

The epsilon net is a parachute-like device that you launch to cover any convex shape. (A shape is convex when, for every pair of points pp and qq it contains, it also contains the entire segment pqpq.) The net's shape must include the launch point (0,0)(0, 0).

The General has PP enemy units at fixed positions, and the Colonel has TT friendly units. The advantage of a chosen net shape equals the number of enemy units it covers minus the number of friendly units it covers. (The General is not a unit.)

You may assume that:

  • no three of the points (Trapp's position (0,0)(0, 0), the enemy units, and the friendly units) lie on a single line;
  • every two points have distinct xx-coordinates and distinct yy-coordinates;
  • every unit has y>0y > 0;
  • all coordinates are integers whose absolute value is at most 10910^9;
  • the total number of units satisfies 1≤P+T≤1001 \le P + T \le 100.

Input

The first line contains PP and TT, separated by a space. Each of the next PP lines contains the coordinates xx and yy of an enemy unit. Each of the following TT lines contains the coordinates of a friendly unit.

Output

Print a single line containing the maximum possible advantage.

Note

Figure 1: the sample input together with one optimal net.

Examples5

  1. Example 1

    Input
    5 3
    -8 4
    -7 11
    4 10
    10 5
    8 2
    -5 7
    -4 3
    5 6
    
    Expected output
    3
    
  2. Example 2

    Input
    3 0
    -5 3
    5 4
    3 8
    
    Expected output
    3
    
  3. Example 3

    Input
    1 0
    3 5
    
    Expected output
    1
    
  4. Example 4

    Input
    0 1
    3 5
    
    Expected output
    0
    
  5. Example 5

    Input
    1 1
    7 2
    -6 9
    
    Expected output
    1