题目描述

Luca 站在一排共有 $n$ 棵树前。第 $i$ 棵树上有 $a_i$ 个果实，高度为 $h_i$。

他想选择一个连续子数组 $[h_l, h_{l+1}, \dots, h_r]$，使得对于每个 $i$（$l \leq i < r$），$h_i$ 能被 $h_{i+1}$ 整除。然后他会收集该子数组中所有树上的果实（即收集 $a_l + a_{l+1} + \dots + a_r$ 个果实）。但是，如果他收集的果实总数超过 $k$，他就会被抓住。

Luca 能选择的最长连续子数组长度是多少，且不会被抓住？

$^\dagger$ 若 $x$ 能被 $y$ 整除，则 $\frac{x}{y}$ 是整数。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq k \leq 10^9$），分别表示树的数量和 Luca 能收集而不被抓住的最大果实数。

每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^4$），表示第 $i$ 棵树上的果实数。

每个测试用例的第三行包含 $n$ 个用空格分隔的整数 $h_i$（$1 \leq h_i \leq 10^9$），表示第 $i$ 棵树的高度。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的最长连续子数组的长度。如果不存在这样的子数组，输出 $0$。

样例

5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2

3
2
1
0
3

样例说明

在第一个测试用例中，Luca 可以选择 $l=1$ 且 $r=3$ 的子数组。

在第二个测试用例中，Luca 可以选择 $l=3$ 且 $r=4$ 的子数组。

在第三个测试用例中，Luca 可以选择 $l=2$ 且 $r=2$ 的子数组。

由 ChatGPT 4.1 翻译

来源

Codeforces 1873F，英文题名 Money Trees。