数轴上有 n 个黑点,坐标为 a[];n 个白点,坐标为 b[](下标均从 0 开始)。同时你有两个参数 la 和 lb,满足 n≥2 且 1≤lb<la。注意同一个位置可能有多个点。
你需要找到一个 0 到 n−1 的排列 p[],满足对于所有 i,有 a[i]≤b[p[i]]≤a[i]+la。你需要最大化满足 b[p[i]]≤a[i]+lb 的下标 i 的个数。数据保证存在一个合法的排列。
输入格式
第一行,三个正整数 n,la,lb。
接下来一行,n 个正整数,表示 a[]。
接下来一行,n 个正整数,表示 b[]。
输出格式
输出一行一个非负整数,表示满足条件的下标个数。
样例数据
样例输入
3 5 1
1 2 5
4 6 7
样例输出
1
样例解释
n=3,la=5,lb=1
a[]={1,2,5}
b[]={4,6,7}
一种最好的排列是 p[]={0,2,1},b[p[2]]=b[1]=6 和 a[2]=5 的差不超过 lb=1,其他均不满足这个条件,答案为 1。
p[]={2,0,1} 不是合法的排列,因为 b[2]=7 被 a[0]=1 匹配,它们的差为 6,超过了 la=5。
p[]={1,2,0} 不是合法的排列,因为 b[0]=4 被 a[2]=5 匹配,但不满足 b[0]≥a[2]。
p[]={0,1,2} 虽然是合法的排列,但是答案为 0,不是最优解。
子任务
子任务 1(4 分):满足 n≤10。
子任务 2(14 分):满足 n≤100。
子任务 3(37 分):满足 n≤5000。
子任务 4(16 分):满足 la=5×105。
子任务 5(29 分):无特殊限制。
对于所有数据,2≤n≤5×105,1≤a[i],b[i]≤5×105,1≤lb≤la≤5×105。保证存在一个合法的排列。