[solution] Reaper Reaps solution codechef – little bits and big deals

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 $N$ houses. The $i$ -th of them has a safety level of $A_{i}$ and has $B_{i}$ people living in it.

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

If $L \geq A_{i}$ , the Reaper will reap the souls of all $B_{i}$ people living in the house.
If $L < A_{i}$ , this does not happen.
Next, $L$ becomes equal to $A_{i}$ , 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 $M$ special houses, which must be visited in a specific order.
You are given this information as an array $C = [C_{1}, C_{2}, \dots, C_{M}]$ containing $M$ distinct integers — where the $C_{i}$ -th house must be visited before the $C_{i + 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 $T$ , 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 $N$ and $M$ — the number of houses and the size of array $C$ respectively.
- The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ — the safeties of the houses.
- The second line of each test case contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$ — the number of people in each house.
- The fourth line of each test case contains $M$ space-separated integers $C_{1}, C_{2}, \dots, C_{M}$ , representing the array $C$ .

In particular, if $M = 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 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$0 \leq M \leq N$
$1 \leq A_{i} \leq 1 0^{5}$
$1 \leq B_{i} \leq 1 0^{4}$
$1 \leq C_{i} \leq N$
All the $C_{i}$ are distinct.
The sum of $N$ over all test cases won’t exceed $3 \cdot 1 0^{5}$ .

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, $L = 0$ .
For house $3$ , $A_{3} = 2 > 0$ , so no souls are reaped. After this, $L$ changes to $2$ .
For house $4$ , $A_{4} = 1 \leq 2$ , so $B_{4} = 2$ souls are reaped. After this, $L$ changes to $1$ .
For house $1$ , $A_{1} = 5 > 1$ , so no souls are reaped. After this, $L$ changes to $5$ .
For house $2$ , $A_{2} = 4 \leq 5$ , so $B_{2} = 1$ soul is reaped. After this, $L$ changes to $4$ .
For house $5$ , $A_{5} = 3 \leq 4$ , so $B_{5} = 4$ souls are reaped. After this, $L$ 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 \to 5 \to 4 \to 2 \to 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.