# Maximum Number Of Eaten Apples

#### You are given two arrays, each of size ‘N’. The first array named ‘APPLES’ denotes the count of the apples produced by an apple tree on each day for N days. The second array named ‘DAYS’ represents the number of days after which these apples will become inedible.

#### Your task is to find the maximum number of apples you can eat if you decided to eat at most one apple per day.

#### Note :

```
1) It is also possible that the tree doesn’t grow any apples on any particular day, i.e., ’APPLES[i]’ = 0 for ‘i’th day.
2) ‘DAYS[i]’ = 0 if and only if ‘APPLES[i]’ = 0.
3) You can keep eating apples even after ‘N’ days, but keep in mind that you can eat at most one apple per day.
```

##### Input Format :

```
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a positive integer ‘N’ denoting the size of the arrays.
The second line of each test case contains N space-separated non-negative integers denoting the elements of the array ‘APPLES’.
The third line of each test case contains N space-separated non-negative integers denoting the elements of the array ‘DAYS’.
```

##### Output Format :

```
For each test case, print the maximum number of apples you can eat.
Output for each test case will be printed in a separate line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 100
1 <= N <= 3000
0 <= ‘APPLES[i]’, ‘DAYS[i]’ <= 3000
Where 'APPLE[i]' and 'DAYS[i]' denotes the ith element of respective array.
Time Limit: 1sec
```

The idea here is to eat the apples that become inedible first than those who become inedible last. For this, we need a structure to keep the apples sorted according to their finish time. We need counts and the expiry date of all apples. Which **data structure** can we use to tackle this kind of scenario? Yes, you are absolutely right. The answer is a **priority queue**. Initialize a **min** priority queue to store the count and the expiry date of apples produced on ‘i’th day. Now, start** inserting** the count and the expiration date of the apples produced on the ‘**i’**th day. After insertion, we have to **remove** those apples that have expired already from the priority queue. Then just add 1 to the answer and **decrement** the count of the top apple of the priority queue it is **not empty**.

**Steps:**

- As we need count and the expiry date of apples together so, we can use a
**pair**. - Initialize a
**min priority queue**named**pq**to store the pair. The**1st**element of the pair is the**expiration**date and**2nd**is the**count**of the ‘i’th apples. - Declare two variables named
**i**= 0, and**ans**= 0. - Run a
**while**loop until any of the 2 conditions are true that are**i**<**‘N’**or**pq**is not empty and in each iteration do:- If ‘
**i’**<**‘N’**and**‘APPLES**[**i**]’ not**0**, then push the pair {i+’DAYS[i]’-1, ‘APPLES[i]’} in the**pq**which is nothing but the expiration date and the count of apples produced on the ‘i’th day. - Run a
**while**loop until both the conditions are true:**pq**is not empty and**pq.top().first**expired, in each iteration:- Pop the top element from the
**pq**.

- Pop the top element from the
- If
**pq**not empty, then:- Increment the
**ans**by 1. - Take the top element in the variable temp,
**temp**=**pq**.top(). - Pop the top element,
**pq**.pop(). - If
**temp.second**> 1, then insert it again after the decrementation in its count, i.e.,**pq.**insert({**temp**.first,**temp**.second-1}).

- Increment the
- Increment i by 1.

- If ‘
- Finally, return
**ans**.