在世界上的某个角落，住着一位懒惰的程序员 Batyr。他最近找到了一份新工作，并想要为接下来的 $N$ 天制定一个工作计划。在第 $i$ 天，Batyr 会收到 $b_i$ 个需要完成的新任务。公司有常规的发布礼仪，因此 Batyr 在第 $i$ 天收到的所有任务必须在第 $\min(N, i + D - 1)$ 天之前（含当天）完成，其中 $D$ 是一个已知的整数。

Batyr 计算出，如果他集中精力在第 $i$ 天工作，他最多可以完成 $a_i$ 个任务。反之，如果 Batyr 决定在第 $i$ 天不工作，那么他在这一天将无法完成任何任务。需要注意的是，在第 $i$ 天，Batyr 只能处理来自第 $j \le i$ 天的任务。

虽然 Batyr 是一个懒惰的程序员，但他很诚实。因此，他必须完成所有的任务。请问 Batyr 为了完成所有任务，最少需要工作多少天？

输入格式

第一行包含一个整数 $t$ —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $D$ ($1 \le D \le N \le 5 \cdot 10^5$)。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 10^9$) —— Batyr 在第 $i$ 天最多能完成的任务数。

每个测试用例的第三行包含 $N$ 个整数 $b_1, b_2, \dots, b_N$ ($0 \le b_i \le 10^9$) —— 在第 $i$ 天出现的新任务数量。

保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— Batyr 完成所有任务所需的最少工作天数。如果无法完成，输出 $-1$。

子任务

$\text{sum}N$ 表示所有测试用例中 $N$ 的总和。

样例

输入 1

2
5 3
6 8 7 20 6
8 3 1 5 2
5 5
5 3 4 10 3
2 5 3 4 0

输出 1

3
2

说明

在第一个样例中，Batyr 将在第 2, 4, 5 天工作。 在第二个样例中，Batyr 将在第 3, 4 天工作。