Under construction

Still being built. Things may change

Hipercampo

Interview

Time limit1sMemory limit1024 MB

Summary
Given two anchors on the x-axis and N points above, choose the largest subset whose segments to both anchors meet only at the anchors.
Level

Medium6 of 10

Topics
Geometry, Sorting, Dynamic programming, Intervals
Solved
No attempts yet

Problem

You are given two anchors, the points A=(XA,0)A = (X_A, 0) and B=(XB,0)B = (X_B, 0) with 0<XA<XB0 < X_A < X_B, which form a horizontal segment. You are also given a set PP of NN points (X,Y)(X, Y) with X>0X > 0 and Y>0Y > 0. The leftmost picture below is one possible input.

To connect a point v∈Pv \in P you draw both segments (v,A)(v, A) and (v,B)(v, B). You want to connect several points, but the drawn segments must meet only at the anchors. Points 1 and 4 in the middle picture cannot both be connected, because their segments would cross somewhere other than an anchor. The rightmost picture shows that points 8, 5 and 3 can be connected together, with the segments meeting only at the anchors.

Compute the largest number of points that can be connected so that the segments meet only at the anchors.

Input

The first line contains three integers NN (1≤N≤1001 \le N \le 100), XAX_A and XBX_B (0<XA<XB≤1040 < X_A < X_B \le 10^4). NN is the number of points in the set PP, and XAX_A and XBX_B are the xx coordinates of the anchors AA and BB. Each of the next NN lines contains two integers XiX_i and YiY_i (0<Xi,Yi≤1040 < X_i, Y_i \le 10^4), the coordinates of the ii th point, for 1≤i≤N1 \le i \le N. No two points share a position, and there are no two distinct points uu and vv such that {A,u,v}\{A, u, v\} is collinear or {B,u,v}\{B, u, v\} is collinear.

Output

Print one line with one integer, the largest number of points of PP that can be connected so that the segments meet only at the anchors.

Examples2

  1. Example 1

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

    Input
    2 2 8
    3 4
    7 4
    
    Expected output
    1