3001 - 神秘的水井

在一个神秘的岛上,有许许多多水井,水井只有两种,圆井和方井,两种井各有n个,水井两两相通。 如果两个水井形状相同,则水井下通道的流向是不确定的。可以任意修改。 如果两个水井形状不同,则水井下通道的流向是确定的。若两个水井间的距离Dij>D,则圆井流向方井,否则方井流向圆井。 这里的Dij指的是曼哈顿距离(|xi-xj|+|yi-yj|),D为给定值 如果某三个井i,j,k,它们形状不完全相同,且它们之间的连的边是 i→j,j→k,k→i。那么就会出现一次灵异现象。 现在要问的是,通过改变同形状水井通道的流向,使得灵异现象出现的最多次和最少次。

输入

第一行两个正整数 N D 接下来N行Xi Yi描述第i个圆井的坐标 再接下来N行Xj Yj描述第j个方井的坐标

输出

两个数依次为灵异现象出现最少的次数,最多的次数,中间用一个空格隔开。

样例

输入

2 1
1 2
1 1
3 1
2 2 

输出

0 2
100% N<=100000 1<=x,y,d<=100000且为整数
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题