Như chúng ta đều biết, bò Bessie không thích gì hơn việc gây rắc rối trong trang trại. Để ngăn cô gây quá nhiều phiền toái, Farmer John quyết định dùng một sợi dây dài buộc Bessie vào hàng rào. Khi nhìn từ trên xuống, hàng rào gồm \(N\) cọc (\(1 \le N \le 10\)) được bố trí dọc theo một đường thẳng đứng, còn vị trí \((bx, by)\) của Bessie nằm bên phải đường thẳng đứng này. Sợi dây FJ dùng để buộc Bessie được mô tả bằng một dãy gồm \(M\) đoạn thẳng (\(3 \le M \le 10\,000\)), trong đó đoạn đầu tiên bắt đầu tại vị trí của Bessie và đoạn cuối cùng kết thúc tại vị trí của Bessie. Không có cọc rào nào nằm trên bất kỳ đoạn thẳng nào trong số này. Tuy nhiên, các đoạn thẳng có thể cắt nhau và nhiều đoạn thẳng có thể trùng nhau tại các đầu mút.

Dưới đây là một ví dụ về quang cảnh khi nhìn từ trên xuống:

Để giúp Bessie trốn thoát, những con bò còn lại đã lấy trộm một chiếc cưa từ nhà kho. Hãy xác định số cọc rào ít nhất mà chúng phải cưa và dỡ bỏ để Bessie có thể giật dây thoát ra (nghĩa là cô có thể chạy sang phải mà sợi dây không mắc vào bất kỳ cọc rào nào).

Tất cả tọa độ \((x,y)\) trong dữ liệu vào (của cọc rào, Bessie và các đầu mút đoạn thẳng) đều nằm trong khoảng từ 0 đến \(10\,000\). Mọi cọc rào có cùng tọa độ \(x\), và \(bx\) lớn hơn giá trị này.

Dữ liệu vào

• Dòng 1 chứa bốn số nguyên \(N\), \(M\), \(bx\) và \(by\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa tọa độ \(x\) và \(y\) của cọc rào \(i\), cách nhau bởi dấu cách.
• Các dòng từ \(2+N\) đến \(2+N+M\): Mỗi dòng trong số \(M+1\) dòng này lần lượt chứa tọa độ \(x\) và \(y\) của một điểm trên sợi dây, cách nhau bởi dấu cách. Điểm đầu tiên và điểm cuối cùng luôn trùng với vị trí \((bx, by)\) của Bessie.

Dữ liệu ra

• Dòng 1 chứa số cọc ít nhất cần dỡ bỏ để Bessie có thể trốn thoát bằng cách chạy sang phải.

Ví dụ

2 10 6 1
2 3
2 1
6 1
2 4
1 1
2 0
3 1
1 3
5 4
3 0
0 1
3 2
6 1

1

Nguồn

USACO 2012 US Open, Gold Division — Tied Down

Tác giả: Brian Dean, 2012.