Gym - 100187F

59 阅读 0 评论 39 点赞

我是靠谱客的博主缓慢夕阳，最近开发中收集的这篇文章主要介绍Gym - 100187F，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Doomsday comes in t units of time. In anticipation of such a significant event n people prepared m vaults in which, as they think, it will be possible to survive. But each vault can accommodate only k people and each person can pass only one unit of distance per one unit of time. Fortunately, all people and vaults are now on the straight line, so there is no confusion and calculations should be simple.

You are given the positions of the people and the vaults on the line. You are to find the maximal number of people who can hide in vaults and think they will survive.

Input

The first line contains four integers n, m, k and t (1 ≤ n, m, k ≤ 200000, 1 ≤ t ≤ 10⁹) separated by spaces — the number of people, the number of vaults, the capacity of one vault and the time left to the Doomsday.

The second line contains n integers separated by spaces — the coordinates of the people on the line.

The third line contains m integers separated by spaces — the coordinates of the vaults on the line.

All the coordinates are between - 10⁹ and 10⁹, inclusively.

Output

Output one integer — the maximal number of people who can hide in vaults and think they will survive.

Example

Input

2 2 1 5
45 55
40 60

Output

Input

2 2 1 5
45 54
40 60

Output

Input

2 2 2 5
45 35
40 60

Output

Input

3 3 1 5
40 45 45
45 50 50

Output

思路：贪心问题，把棺材作为研究对象，从左到右遍历一遍即可；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int peo[200005],res[200005];
int main()
{
int n,m,k,t;
while(scanf("%d %d %d %d",&n,&m,&k,&t)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&peo[i]);
for(int i=0;i<m;i++)
scanf("%d",&res[i]);
sort(peo,peo+n);
sort(res,res+m);
int now=0,cnt=0,ans=0;
for(int i=0;i<m;i++)
{
cnt=k;
int j=now;
for(;peo[j]<=res[i]+t && j<n && cnt;j++)
{
if(peo[j]>=res[i]-t)
{
ans++;
cnt--;
}
}
now=j;
if(j==n) break;
}
printf("%dn",ans);
}
return 0;
}