E. Double Cut
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mike Angel has a rectangular sheet of paper of width $$$a$$$ and height $$$b$$$. He wants to cut out a convex polygon with $$$n$$$ vertices.

The paper initially occupies the rectangle with corners $$$(0,0)$$$, $$$(a,0)$$$, $$$(a,b)$$$, and $$$(0,b)$$$. The polygon's vertices are distinct and listed in clockwise or counterclockwise order. Consecutive vertices are joined by edges, including the last and first vertices. The polygon is simple and convex, and no three of its vertices are collinear. The polygon lies entirely within the paper, and its vertices or edges may lie on the paper's boundary.

Mike can perform a series of double cuts. In each operation, he does the following to the piece of paper he currently has:

  1. Choose a point $$$P$$$ in the piece, possibly on its boundary.
  2. Choose two points $$$A$$$ and $$$B$$$ on the boundary of the piece.
  3. Cut along the segments $$$PA$$$ and $$$PB$$$, which must lie entirely within the piece. Keep one of the resulting pieces and discard the others.

The chosen points may have non-integer coordinates and need not be vertices of the desired polygon. The two segments may lie on the same straight line, so a straight cut is also allowed as one double cut. Subsequent operations use only the piece kept after the previous operation.

Find the minimum number of double cuts needed so that the remaining piece is exactly the desired polygon. Mike may perform zero cuts.

Input

The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$3 \le n \le 10^5$$$, $$$1 \le a,b \le 10^9$$$) — the number of vertices of the polygon, the width of the paper, and the height of the paper, respectively.

The second line contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$0 \le x_i \le a$$$) — the $$$x$$$-coordinates of the vertices in order.

The third line contains $$$n$$$ integers $$$y_1,y_2,\ldots,y_n$$$ ($$$0 \le y_i \le b$$$) — the $$$y$$$-coordinates of the vertices in the same order.

The vertices are distinct and form a simple, convex polygon in clockwise or counterclockwise order. No three vertices are collinear.

Output

Output a single integer — the minimum number of double cuts needed to cut out the polygon.

Example
Input
3 1 2
0 1 1
1 0 2
Output
1
Note

In the sample, Mike can choose $$$P=(0,1)$$$, $$$A=(1,0)$$$, and $$$B=(1,2)$$$. Cutting along $$$PA$$$ and $$$PB$$$ leaves the desired triangle as one piece. The triangle differs from the original rectangle, so at least one cut is necessary. Thus, the answer is $$$1$$$.

The diagram below illustrates this double cut.