Alexa has two stacks of non-negative integers, stack** A=[a _{0},a_{1},…….a_{m-1}] **and stack

**B=[b**where index

_{0},b_{1},…………b_{n-1}]**0**denotes the top of the stack. Alexa challenges Nick to play the following game Game of Two Stacks Hackerrank :

- In each move, Nick can remove one integer from the top of either stack A or stack B.
- Nick keeps a running sum of the integers he removes from the two stacks.
- Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer x given at the beginning of the game.
- Nick’s
*final score*is the total number of integers he has removed from the two stacks.

Given** A, B**, and **x** for **g** games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

**Input Format for Game of Two Stacks Hackerrank**

The first line contains an integer, **g** (the number of games). The **3.g** subsequent lines describe each game in the following format:

- The first line contains three space-separated integers describing the respective values of
**m**(the number of integers in stack**A**),**n**(the number of integers in stack**B**), and**x**(the number that the sum of the integers removed from the two stacks cannot exceed). - The second line contains m space-separated integers describing the respective values of
**a**a_{0},a_{1},…………_{-m-1} - The third line contains n space-separated integers describing the respective values of
**b**_{0},b_{1},…………b_{n-1}.

**Sample Input 0**

```
1
5 4 10
4 2 4 6 1
2 1 8 5
```

**Sample Output 0**

```
4
```

**Explanation 0**

The two stacks initially look like this:

The image below depicts the integers Nick should choose to remove from the stacks. We print **4** as our answer because that is the maximum number of integers that can be removed from the two stacks without the sum exceeding **x=10**.

(There can be multiple ways to remove the integers from the stack, the image shows just one of them.)

### Solution

This problem can be solved in linear time. We’ll begin by taking as many integers as possible from stack **A** without exceeding the sum. Once we’ve done this we’ll start taking integers from **B**, but whenever the sum becomes larger than the limit, we’ll put integers back into stack **A**. Make sure to update the answer (the number of integers) as the traversal through stack **B** takes place. Break the loop when you have put back all integers that were taken from **A** and it’s not possible to take any more integers from B.

#### C++

```
// vkreddy21 thanks to you.
#include <bits/stdc++.h>
using namespace std;
int main(){
int g;
cin >> g;
for(int a0 = 0; a0 < g; a0++){
int n;
int m;
int x;
cin >> n >> m >> x;
vector<int> a(n);
for(int a_i = 0; a_i <n; a_i++){
cin >> a[a_i];
}
vector<int> b(m);
for(int b_i =0; b_i <m; b_i++){
cin >> b[b_i];
}
int sum=0,count=0,temp=0,i=0,j=0;
while(i<n && sum+a[i]<=x){ //considering only first stack and calculating count
sum+=a[i];
i++;
}
count=i;
while(j<m && i>=0){ //now adding one element of second stack at a time and subtracting the top element of first stack and calculating the count
sum+=b[j];
j++;
while(sum>x && i>0){
i--;
sum-=a[i];
}
if(sum<=x && i+j>count)
count=i+j;
}
cout<<count<<endl;
}
return 0;
}
```

#### C

```
#include <bits/stdc++.h>
using namespace std;
int A[100002],B[100002];
int main(){
int t;
cin >> t;
while (t--) {
int n, m ,ms;
scanf("%d%d%d", &n, &m, &ms);
for(int A_i = 0; A_i < n; A_i++){
scanf("%d",&A[A_i]);
}
for(int B_i = 0; B_i < m; B_i++){
scanf("%d",&B[B_i]);
}
long long sum = 0;
int x = 0, y = 0;
while (x < n && sum + A[x] <= ms) {
sum += A[x++];
}
int ans = x;
while (y < m && x >= 0) {
sum += B[y++];
while (sum > ms && x > 0) {
sum -= A[--x];
}
if (sum <= ms && ans < x + y) {
ans = x + y;
}
}
printf("%d\n",ans);
}
return 0;
}
```