← 返回题目列表

Codeforces · 1873/F

F. 金钱树

中文机器翻译题面 查看原题

卢卡在一排 $$$n$$$ 树前面。第 $$$i$$$ 树有 $$$a_i$$$ 果实,高度 $$$h_i$$$。

他想要选择数组 $$$[h_l, h_{l+1}, \dots, h_r]$$$ 的连续子数组,这样对于每个 $$$i$$$ ($$$l \leq i < r$$$),$$$h_i$$$ 可以整除 $$$^{\dagger}$$$ $$$h_{i+1}$$$。他将从子数组中的每棵树上收集所有水果(也就是说,他将收集 $$$a_l + a_{l+1} + \dots + a_r$$$ 水果)。然而,如果他收集的水果总数超过$$$k$$$,他就会被抓住。

Luca 可以选择的子数组的最大长度是多少,这样他就不会被抓住?

如果比率 $$$\frac{x}{y}$$$ 是整数,则 $$$^{\dagger}$$$ $$$x$$$ 可以被 $$$y$$$ 整除。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例行的第一个包含两个空格分隔的整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq 10^9$$$) - 树的数量和卢卡在不被抓住的情况下可以收集的最大水果数量。

每个测试用例的第二行包含 $$$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$$$。

示例

输入 #1

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

输出 #1

3
2
1
0
3

注意

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

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

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