# [solution] Reaper Reaps solution codechef

## Problem solution codechef

I have no compassion, I only exist to collect the souls of the living.

On Halloween, Grim Reaper wants to reap souls from houses.
There are  houses. The -th of them has a safety level of �� and has �� people living in it.

The Reaper has an ability level, denoted . Initially, �=0.
When the Reaper visits a house, the following two things happen in order:

• If �≥��, the Reaper will reap the souls of all �� people living in the house.
If �<��, this does not happen.
• Next,  becomes equal to ��, the safety level of the house.
This change occurs whether souls were reaped or not.

The Reaper will visit each house exactly once, in some order.
However, there are  special houses, which must be visited in a specific order.
You are given this information as an array �=[�1,�2,…,��] containing  distinct integers — where the ��-th house must be visited before the ��+1-th house.

Find the maximum possible number of souls the Reaper can reap, if the order of visiting houses is chosen optimally under the given conditions.

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of four lines of input.
• The first line of each test case contains two space-separated integers  and  — the number of houses and the size of array  respectively.
• The second line of each test case contains  space-separated integers �1,�2,…,�� — the safeties of the houses.
• The second line of each test case contains  space-separated integers �1,�2,…,�� — the number of people in each house.
• The fourth line of each test case contains  space-separated integers �1,�2,…,��, representing the array .

In particular, if �=0, the fourth line of input will be blank.

### Output Format

For each test case, output on a new line the maximum number of souls that reaper can collect.

### Constraints

• 1≤�≤105
• 1≤�≤105
• 0≤�≤�
• 1≤��≤105
• 1≤��≤104
• 1≤��≤�
• All the �� are distinct.
• The sum of  over all test cases won’t exceed 3⋅105.

### Sample 1:

Input

Output

3
5 5
5 4 2 1 3
8 1 10 2 4
3 4 1 2 5
5 2
5 4 2 1 3
8 1 10 2 4
5 2
7 0
6 8 4 3 5 8 2
7 2 8 1 6 8 1

7
16
31

### Explanation:

Test case 1: Reaper has no choice but to visit houses in order [3,4,1,2,5]. The process is as follows:

• Initially, �=0.
• For house 3�3=2>0, so no souls are reaped. After this,  changes to 2.
• For house 4�4=1≤2, so �4=2 souls are reaped. After this,  changes to 1.
• For house 1�1=5>1, so no souls are reaped. After this,  changes to 5.
• For house 2�2=4≤5, so �2=1 soul is reaped. After this,  changes to 4.
• For house 5�5=3≤4, so �5=4 souls are reaped. After this,  changes to 3, and the process is done.

In total, 1+2+4=7 souls are reaped.

Test case 2: The Reaper can visit houses in any order, as long as 5 is visited before 2.
In this case, one optimal order is to visit 1→5→4→2→3, which reaps 10+2+4=16 souls.
It can be proved that this is the maximum possible.

Test case 3: It can be proved that we can not reap more than 31 souls.