# [Solution] Training Plans solution codechef

Training Plans solution codechef – Nathan is preparing for the Dash marathon. He has NN training plans. The ii-th plan has an effectiveness of AiAi, but requires that at least BiBi other training plans must be performed before it. A training plan cannot be repeated.

# Training Plans solution codechef

If he performs some K>0K>0 distinct trainings – P1,P2,,PKP1,P2,…,PK (1PiN,PiPj)(1≤Pi≤N,Pi≠Pj) then his training score is Kj=1APjK∑j=1KAPjK. If Nathan does not perform any training plan (K=0)(K=0), then his score is 00.

What is the highest score that Nathan can get by performing zero or more training plans, if he can perform them in any order?

### Input Format

• The first line of the input contains a single integer TT – the number of test cases. The description of TT test cases follows.
• The first line of each test case contains NN – the number of training plans.
• The second line contains NN integers A1,A2,,ANA1,A2,…,AN where AiAi is the effectiveness of the ii-th training plan.
• The third line contains NN integers B1,B2,,BNB1,B2,…,BN where BiBi is the number of pre-requisite training plans for the ii-th training plan.

### Output Format

• For each test case, output a single real number – the highest score that Nathan can get by performing zero or more training plans.

## Training Plans solution codechef

• 1T10001≤T≤1000
• 1N1051≤N≤105
• 105Ai105−105≤Ai≤105
• 0BiN10≤Bi≤N−1
• Sum of NN over all test cases does not exceed 51055⋅105.

### Sample Input 1

3
4
-9 -21 -4 -43
0 0 0 0
5
10 14 5 9 1
4 1 3 0 0
7
-1 101 5 63 -7 -88 59
0 1 6 2 3 4 5


### Sample Output 1

0.000000
11.500000
54.333333


## Training Plans solution codechef Explanation

Test case 1: It is optimal for Nathan to not perform any training plans as all the plans have negative AiAi value.

Test case 2: It is optimal for Nathan to:

• First, perform the 44-th training plan (for which Bi=0Bi=0).
• Then perform the 22-nd training plan (for which Bi=1Bi=1 which is satisfied as he has already performed 11 training plan)

Test case 3: It is optimal for Nathan to:

• First, perform the 11-st training plan (for which Bi=0Bi=0).
• Then perform the 22-nd training plan (for which Bi=1Bi=1 which is satisfied as he has already performed 11 training plan)
• Then perform the 44-th training plan (for which Bi=2Bi=2 which is satisfied as he has already performed 22 training plans)