You have obtained the new limited event character Xilonen. You decide to use her in combat.

There are $n$ enemies in a line. The $i$'th enemy from the left has health $h_i$ and is currently at position $x_i$. Xilonen has an attack damage of $m$, and you are ready to defeat the enemies with her.

Xilonen has a powerful "ground stomp" attack. Before you perform any attacks, you select an integer $p$ and position Xilonen there ($p$ can be any integer position, including a position with an enemy currently). Afterwards, for each attack, she deals $m$ damage to an enemy at position $p$ (if there are any), $m-1$ damage to enemies at positions $p-1$ and $p+1$, $m-2$ damage to enemies at positions $p-2$ and $p+2$, and so on. Enemies that are at least a distance of $m$ away from Xilonen take no damage from attacks.

Formally, if there is an enemy at position $x$, she will deal $\max(0,m - |p - x|)$ damage to that enemy each hit. Note that you may not choose a different $p$ for different attacks.

Over all possible $p$, output the minimum number of attacks Xilonen must perform to defeat at least $k$ enemies. If it is impossible to find a $p$ such that eventually at least $k$ enemies will be defeated, output $-1$ instead. Note that an enemy is considered to be defeated if its health reaches $0$ or below.

Input

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of test cases.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \leq k \leq n \leq 10^5$, $1 \leq m \leq 10^9$).

The following line contains $n$ integers $h_1, h_2, ..., h_n$ ($1 \leq h_i \leq 10^9$).

The last line of each testcase contains $n$ integers $x_1, x_2, ..., x_n$ ($1\leq x_i \leq 10^9$, $x_i < x_{i+1}$ for all $1 \leq i < n$)

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output an integer on a new line, the minimum number of attacks that must be performed to defeat at least $k$ enemies. If it is impossible to find a $p$ such that eventually at least $k$ enemies will be defeated, output $-1$ instead.

见题面 Input 部分

见题面 Output 部分

In the first testcase, it is optimal to select $p=2$. Each attack, the first enemy takes $5-|2-1|=4$ damage, the second enemy takes $5$ damage, the third enemy takes $4$ damage, the fourth enemy takes $3$ damage, and the fifth enemy takes $2$ damage. After $2$ attacks, the first three enemies will be defeated. It can be shown that it is impossible to defeat $3$ enemies in less than $2$ attacks, no matter which $p$ is selected.

In the second testcase, we must kill all $9$ enemies. By selecting $p=5$, all nine enemies will be defeated in $2$ attacks.

In the third testcase, we must kill both enemies. However, it can be shown that no $p$ selected will damage both enemies at the same time, so the answer is $-1$.

In the fourth testcase, selecting $p=1$ will enable us to defeat the first enemy in $6969697$ attacks.

In the fifth testcase, selecting $p=10$ will make each enemy take $1$ damage per attack. Both enemies will be defeated in $15$ attacks.