杂题——Money Trees

Money Trees

原题

Luca is in front of a row of $n$ trees. The $i$-th tree has $a_i$ fruit and height $h_i$.

He wants to choose a contiguous subarray of the array $[h_l, h_{l+1}, \dots, h_r]$ such that for each $i$ ($l \leq i < r$), $h_i$ is divisible$^{\dagger}$ by $h_{i+1}$. He will collect all the fruit from each of the trees in the subarray (that is, he will collect $a_l + a_{l+1} + \dots + a_r$ fruits). However, if he collects more than $k$ fruits in total, he will get caught.

What is the maximum length of a subarray Luca can choose so he doesn’t get caught?

$^{\dagger}$ $x$ is divisible by $y$ if the ratio $\frac{x}{y}$ is an integer.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first of each test case line contains two space-separated integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq 10^9$) — the number of trees and the maximum amount of fruits Luca can collect without getting caught.

The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^4$) — the number of fruits in the $i$-th tree.

The third line of each test case contains $n$ space-separated integers $h_i$ ($1 \leq h_i \leq 10^9$) — the height of the $i$-th tree.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case output a single integer, the length of the maximum length contiguous subarray satisfying the conditions, or $0$ if there is no such subarray.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

output

1
2
3
4
5
3
2
1
0
3

翻译

卢卡在一排 $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$ 个，他就会被抓住。

卢卡可以选择的子数组的最大长度是多少，这样他就不会被抓住？

如果比率 $\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$ ) - 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$ 。

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

output

1
2
3
4
5
3
2
1
0
3

笔记

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

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

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

思路

创建l，r指针，r满足向右走sum+=a[r],r++，不满足l向右走sum-=a[l],l–;

当l==r使,r向右走

当高度不满足时，重新累计sum=0,l指针直接转向r，r++；

然后取r-l最大的区间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N=2e5+10;
int a[N],b[N];

void solve() {
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	int l=1,r=1,sum=0,mx=0;
	while(l<=n&&r<=n){
		if(l==r) sum+=a[l],r++;
		else if(b[r-1]%b[r]==0) sum+=a[r],r++;
		else l=r,sum=0;
		while(sum>k) sum-=a[l],l++;
		mx=max(mx,r-l);	
	}	
	cout<<mx<<ed;
}


int main()
{
    
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}