2677 - [Usaco2012 Open]tied

众所周知,奶牛贝茜最爱的事情就是在农场恶作剧。为了避免她造成太多的麻烦,农夫约翰决定用一根长绳将贝茜 系在栅栏上。从上面俯瞰,围栏由N个x坐标相等的柱子(1<=N<=10)组成,贝茜的位置(bx,by)位于这些柱子组成的 直线的右侧。约翰用来约束贝茜的绳子由M条首尾相接的线段(3<=M<=10,000)构成,其中第一段从贝茜的位置开始 ,最后一段在贝茜的位置结束。保证这些线段上没有栅栏柱;但是线段可能交叉,并且可能有多条线段在端点处重 叠。为了帮助贝茜逃跑,其他的牛从谷仓里偷了一把锯子。请确定为了让贝西能够自由拉动(即她可以在没有绳子 拴住任何栅栏柱的情况下跑到右边),他们必须锯断栅栏杆的最少数量。输入中的所有(x,y)坐标(栅栏柱子、贝 茜和线段端点的位置)位于0至10,000的范围内。所有栅栏柱子都具有相同的x坐标,并且bx大于此值。

Input

第一行四个整数N,M,bx,by。 接下来N行每行输入一根栅栏柱的坐标。 接下来M+1行按顺序输入绳子的端点坐标,保证第一个点和最后一个点与(bx,by)位置相同。

Output

输出一行一个整数:让贝茜走到右侧需要锯断的最少柱子数。

Examples

Input

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
输入解释:有两个柱子(2,3)和(2,1)。贝茜在(6,1)。绳索从(6,1)到(2,4)到(1,1),依此类推,最后终止于(6,1)。

Output

1
输出解释:锯断柱子1或柱子2可以使贝茜逃脱。
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题