B. Born This Way

￡神魔★判官ぃ 2022-01-23 10:13 83阅读 0赞

B. Born This Way

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Arkady bought an air ticket from a city A to a city C. Unfortunately, there are no direct flights, but there are a lot of flights from A to a city B, and from B to C.

There are nn flights from A to B, they depart at time moments a1a1, a2a2, a3a3, ..., anan and arrive at B tata moments later.

There are mm flights from B to C, they depart at time moments b1b1, b2b2, b3b3, ..., bmbm and arrive at C tbtb moments later.

The connection time is negligible, so one can use the ii-th flight from A to B and the jj-th flight from B to C if and only if bj≥ai+tabj≥ai+ta.

You can cancel at most kk flights. If you cancel a flight, Arkady can not use it.

Arkady wants to be in C as early as possible, while you want him to be in C as late as possible. Find the earliest time Arkady can arrive at C, if you optimally cancel kk flights. If you can cancel kk or less flights in such a way that it is not possible to reach C at all, print −1−1.

Input

The first line contains five integers nn, mm, tata, tbtb and kk (1≤n,m≤2⋅1051≤n,m≤2⋅105, 1≤k≤n+m1≤k≤n+m, 1≤ta,tb≤1091≤ta,tb≤109) — the number of flights from A to B, the number of flights from B to C, the flight time from A to B, the flight time from B to C and the number of flights you can cancel, respectively.

The second line contains nn distinct integers in increasing order a1a1, a2a2, a3a3, ..., anan (1≤a1<a2<…<an≤1091≤a1<a2<…<an≤109) — the times the flights from A to B depart.

The third line contains mm distinct integers in increasing order b1b1, b2b2, b3b3, ..., bmbm (1≤b1<b2<…<bm≤1091≤b1<b2<…<bm≤109) — the times the flights from B to C depart.

Output

If you can cancel kk or less flights in such a way that it is not possible to reach C at all, print −1−1.

Otherwise print the earliest time Arkady can arrive at C if you cancel kk flights in such a way that maximizes this time.

Examples

input

Copy

4 5 1 1 2
    1 3 5 7
    1 2 3 9 10

output

Copy

input

Copy

2 2 4 4 2
    1 10
    10 20

output

Copy

-1

input

Copy

4 3 2 3 1
    1 999999998 999999999 1000000000
    3 4 1000000000

output

Copy

1000000003

Note

Consider the first example. The flights from A to B depart at time moments 11, 33, 55, and 77 and arrive at B at time moments 22, 44, 66, 88, respectively. The flights from B to C depart at time moments 11, 22, 33, 99, and 1010 and arrive at C at time moments 22, 33, 44, 1010, 1111, respectively. You can cancel at most two flights. The optimal solution is to cancel the first flight from A to B and the fourth flight from B to C. This way Arkady has to take the second flight from A to B, arrive at B at time moment 44, and take the last flight from B to C arriving at C at time moment 1111.

In the second example you can simply cancel all flights from A to B and you're done.

In the third example you can cancel only one flight, and the optimal solution is to cancel the first flight from A to B. Note that there is still just enough time to catch the last flight from B to C.

**题意:一个人要从A地到C地，会经过B地，有n次航班A到B的时间点，然后花费时间ta，和m次B到C的时间的点，花费时间tb，你有k次操作机会，删掉航班，这样这个人不得不搭乘其他航班，输出经过k次操作后让这个人到达的最晚时间，如果不能到达就输出-1.**

**题解：二分  先遍历删除a最前面的航班，然后找经过i次删除后最早达到B的航班然后在二分查找出最快能搭乘B到C的的航班时间点的下标，如果操作次数有剩余还得删除到达B后能够搭乘的k-i个航班时间点，尽量让这个人不能立即搭乘，如果经过I次操作后，剩下的操作能比能够搭乘的航班次数多，就不能到达。**

c++：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,m,ta,tb,k,a[200010],b[200010],ans=0;
        cin>>n>>m>>ta>>tb>>k;
        for(int i=0; i<n; i++)
            cin>>a[i];
        for(int i=0; i<m; i++)
            cin>>b[i];
        if(k>=n||k>=m)
        {
             puts("-1");
             return 0;
        }
        for(int i=0; i<=k; i++)
        {
            int j=lower_bound(b,b+m,a[i]+ta)-b;
            if(k-i>=m-j)///如果删除a里面的数，剩下k-i次数>=从a机场飞到b后，b机场登机的次数，就不能达到目的地
            {
                puts("-1");
                return 0;
            }
            ans=max(ans,b[j+k-i]+tb);///删掉b机场剩下k-i的登机数，然后找出下一场最早的登机时间
        }
        cout<<ans<<endl;
        return 0;
    }

python：

import bisect
    n,m,ta,tb,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    ans=0
    try:
              for i in range(k+1):
                        j=bisect.bisect_left(b,a[i]+ta)
                        ans=max(ans,b[j+k-i]+tb)
              print(ans)
    except:
              print(-1)