Gold Rush

All submissions for this problem are available.
In a game there are $M$ boxes, each containing $A_j$ grams of gold. In a turn, $N$ chains are kept on the ground with $L_i$ and $R_i$ denoting the coordinates of the left and right end of the $i^{th}$ chain. You are allowed to lock at most one box of gold in each turn. To lock a box containing $A_j$ grams of gold, you need a chain of thickness $P$ and length at least $A_j$. To get a thickness of $P$ you need to join $P$ chains in place (you cannot drag the chains in any direction) and remove the extra part of the chains which are not helping in forming thickness $P$. The length of the resultant (continuous) is the length of the joined chain of thickness $P$. You win the gold present in your $locked$ box. Given $T$ turns with different settings of chains, find the maximum amount of gold you can win in each turn. [All the turns are independent, i.e. if a box was locked in the previous turn, it is unlocked before the next turn.] ###Input:  First line of the input contains a single integer $M$ describing the number of boxes.  Second line of the input contains $M$ space separated integers denoting $A_1, A_2 …. A_M$.  Third line of the input contains a single integer $T$ describing the number of turns. The description of $T$ turns follows:  First line of each turn contains two space separated integers $N$ and $P$.  This is followed by $N$ lines. For each $i$ ($1\leq i \leq N$), the $i^{th}$ of these lines contains two space separated integers $L_i$ and $R_i$. ###Output: For each of the turn, print the weight of gold won in grams. ###Constraints  $1 \leq T \leq 3000$  $1 \leq M \leq 10^6$  $1 \leq P \leq N \leq 10^5$  $1 \leq L_i \leq R_i \leq 10^9$  $1 \leq A_j \leq 10^9$  the sum of $N$ over all test cases does not exceed $6*10^5$ ###Sample Input:5 1 7 3 4 6 2 4 2 1 7 6 9 2 7 1 5 3 2 3 10 4 8 3 5###Sample Output:
6 4
Author:  kishen1912000 
Editorial  https://discuss.codechef.com/problems/GRUSH 
Tags  binarysearch, cnxh2020, easymedium, heaps, kishen1912000 
Date Added:  3012020 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 