Shuttle Bus

题号：NC200123
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

It's the summer holiday! Little Gyro went to Xiaoqikong Scenic Area with his parents Mr./Mrs.Potato, However, there was lots of people and many places were very crowded.

Due to there always exists some distance between most of the scenic spots (shown as the map below), scenic area administrators often control the current pedestrian flow by scheduling the shuttle buses properly.

When the administrators found that the current pedestrian flow of a scenic spot reached the maximum load, they would immediately start to restrict the pedestrian flow by limiting the shuttle buses arriving there.

To simplify the problem, we just consider the situation only with three places A, B and C.
Little Gyro and his parents were at place A, they wanted to go to place C by shuttle bus. There were no direct route from A to C, However, Little Gyro can take shuttle buses from A to B, and from B to C. Little Gyro was looking at the schedule posted at the notice wall, shown the depart time of the place A and B in everyday situation.
There are n shuttle buses from A to B, they depart at time moments $a_1$ , $a_2$ , $a_3$ , ..., $a_n$ and arrive at B $t_a$ moments later.
There are m shuttle buses from B to C, they depart at time moments $b_1$ , $b_2$ , $b_3$ , ..., $b_m$ and arrive at C $t_b$ moments later.
We supposed that the connection time is negligible, so Little Gyro could use the i-th shuttle bus from A to B and the j-th shuttle bus from B to C if and only if $b_j$ ≥ $a_i+t_a$ .
Unfortunately, the people at place C was overloaded, so that the administrator canceled k shuttle buses. If a shuttle bus was canceled, Little Gyro could not take it.
Little Gyro and his parents wanted to be in C as early as possible, while the administrator want them to be in C as late as possible. Find the earliest time Little Gyro can arrive at C, if the administrator optimally cancel k shuttle buses. If the administrator can cancel k or less shuttle buses in such a way that it is not possible to reach C at all, print "Please wait..." (without quotes).

输入描述:

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains five integers n , m ,  ,  and k (1 ≤ n,m ≤ 2× , 1 ≤ k ≤ n+m , 1 ≤  ≤  ) — the number of shuttle buses from A to B, the number of shuttle buses from B to C, the shuttle bus time from A to B, the shuttle bus time from B to C and the number of shuttle buses the administrator can cancel, respectively.
The second line contains n distinct integers in increasing order  (1 ≤  <  <…<  ≤ ) — the times the shuttle buses from A to B depart.
The third line contains m distinct integers in increasing order  (1 ≤  <  <…<  ≤ ) — the times the shuttle buses from B to C depart.
It's guaranteed that the sum of n, m of all test cases will not exceed .

输出描述:

For each test case, If the administrator can cancel k or less shuttle buses in such a way that it is not possible to reach C at all, print “Please wait...” (without quotes).

Otherwise print the earliest time Little Gyro can arrive at C if the administrator cancel k shuttle buses in such a way that maximizes this time.

示例1

输入

复制

3
4 5 1 1 2
1 3 5 7
1 2 3 9 10
2 2 4 4 2
1 10
10 20
4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000

输出

复制

11
Please wait...
1000000003

说明

Consider the first example. The shuttle buses from A to B depart at time moments 1, 3, 5, and 7 and arrive at B at time moments 2, 4, 6, 8, respectively. The shuttle buses from B to C depart at time moments 1, 2, 3, 9, and 10 and arrive at C at time moments 2, 3, 4, 10, 11, respectively. The administrator can cancel at most two shuttle buses. The optimal solution is to cancel the first shuttle bus from A to B and the fourth shuttle bus from B to C. This way Little Gyro has to take the second shuttle bus from A to B, arrive at B at time moment 4, and take the last shuttle bus from B to C arriving at C at time moment 11.
In the second example the administrator can simply cancel all shuttle buses from A to B.
In the third example the administrator can cancel only one shuttle bus, and the optimal solution is to cancel the first shuttle bus from A to B. Note that there is still just enough time to catch the last shuttle bus from B to C.