#P3017. 我是奶龙,别打我,呜呜呜!

我是奶龙,别打我,呜呜呜!

题目描述

nn 个编号为 11nn 的奶龙在坐标轴上,第 ii 个奶龙的生命值为 hih_i,横坐标为 ii,奶龙们的横坐标按编号升序排列。

你可以预先选定一个整数横坐标 pp,并发动任意次数强度为 mm 的攻击。
每次攻击后,第 ii 个奶龙受到 max(0,mpi)\max(0, m - |p - i|) 点伤害;当奶龙生命值降到 00 及以下时,该奶龙就被击败。
注意:pp 在攻击前选定,选定后不能改变。

给定整数 n,m,hi,kn, m, h_i, k,求如何选择 pp,使得能在最少的攻击次数内击败至少 kk 个奶龙。
只需输出最少的攻击次数。

输入格式

  • 第一行一个整数 t (1t100)t\ (1 \le t \le 100),表示测试用例数量。
  • 每个测试用例:
    • 第一行三个整数 $n, m, k\ (1 \le k \le n \le 10^4,\ 1 \le m \le 10^9)$。
    • 第二行 nn 个整数 h1,h2,,hn (1hi109)h_1, h_2, \dots, h_n\ (1 \le h_i \le 10^9)
    • 第三行 nn 个整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9,\ a_i < a_{i+1},\ 1 \le i < n)$。

保证所有测试用例nn的和不超过 10510^5

输出格式

对于每个测试用例,输出一行一个整数,表示击败至少 kk 个敌人所需的最小攻击次数;
若不存在满足条件的 pp,输出 1-1

样例

6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3

2
2
-1
6969697
15
1000000000

样例解释:
在第一个测试用例中,选择p=2p = 2是最优的。每次攻击,第一个敌人受到521=45 - |2 - 1| = 4伤害,第二个敌人受到55伤害,第三个敌人受到44伤害,第四个敌人受到33伤害,第五个敌人受到22伤害。经过22次攻击,第一个三个敌人将被击败。可以证明,无论选择哪个pp,都不可能在少于22次攻击中击败33个敌人。

在第二个测试用例中,我们必须击败所有99个敌人。通过选择p=5p = 5,所有九个敌人将在22次攻击中被击败。

在第三个测试用例中,我们必须击败两个敌人。然而,可以证明没有选择的pp可以同时对两个敌人造成伤害,因此答案是1-1

在第四个测试用例中,选择p=1p = 1将使我们能够在69696976969697次攻击中击败第一个敌人。

在第五个测试用例中,选择p=10p = 10将使每个敌人在每次攻击中受到11伤害。两个敌人将在1515次攻击中被击败。