Cuộc thi điều khiển robot năm nay được tổ chức trên một sân có kích thước ~w \times h~ được mô phỏng trên hệ trục tọa độ ~Oxy~. Tọa độ được đánh thứ tự ~0, 1, 2, ..., w~ từ trái qua phải và ~0, 1, 2, ..., h~ từ dưới lên trên. Các Robot được lập trình di chuyển theo một trong ba hướng sang phải, đi lên, chéo lên với tham số di chuyển ~d~ theo nguyên tắc:

Giả sử robot đang đứng ở tọa độ ~(x, y)~:

• Nếu robot đang quay hướng sang phải, robot sẽ nhảy tới tọa độ ~(x + d, y)~.
• Nếu robot đang quay hướng đi lên, robot sẽ nhảy tới tọa độ ~(x, y + d)~.
• Nếu robot đang quay hướng chéo lên, robot sẽ nhảy tới tọa độ ~(x + d, y + d)~.

Trên sân có ~n~ điểm đặc biệt, điểm thứ ~i~ có tọa độ ~(u_i, v_i)~. Khi nhảy vào một trong các điểm đặc biệt này, robot được phép:

• Giữ nguyên hướng hoặc thay đổi sang một trong hai hướng còn lại.
• Giữ nguyên tham số điều khiển ~d~ hoặc thay đổi thành:
  • ~d' = 2d~: robot tăng gấp đôi khả năng nhảy.
  • ~d' = \frac{d}{2}~: trong trường hợp ~d~ chẵn, robot có thể giảm đi một nửa khả năng nhảy.
  • ~d' = 1~: giảm khả năng nhảy về mức tối thiểu.

Mỗi lần tới một ô đặc biệt, robot được thay đổi tham số điều khiển tối đa một lần.

Yêu cầu: Ban đầu robot được đặt ở tọa độ ~(0, 0)~ và được chọn di chuyển theo một hướng bất kỳ với tham số điều khiển ~d = 1~. Hãy xác định số lần nhảy tối thiểu để robot có thể di chuyển tới tọa độ ~(w, h)~.

Input

• Dòng đầu chứa ba số nguyên ~n, w, h~ (~0 \le n \le 70000; 0 \le w, h \le 10^9~).
• ~n~ dòng sau, dòng thứ ~i~ gồm chứa hai số nguyên ~u_i, v_i~ xác định tọa độ đặc biệt thứ ~i~ (~0 \le u_i \le w; 0 \le v_i \le h~).

Output

• Ghi ra một số nguyên duy nhất là số bước nhảy tối thiểu. Đưa ra ~-1~ trong trường hợp robot không thể đến đích.

Sample Input 1

4 5 4
1 2
5 2
5 0
1 0

Sample Output 1

3

Subtasks