F. Ardent Flamestime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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$$$.OutputFor 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.ExampleInput65 5 37 7 7 7 71 2 3 4 59 5 92 4 6 8 10 8 6 4 21 2 3 4 5 6 7 8 92 10 21 11 202 10 169696969 4204204201 202 10 210 151 192 2 21000000000 11 3Output2
2
-1
6969697
15
1000000000
NoteIn 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.