Play with numbers
All submissions for this problem are available.
In Casino Royal , there was a gambling machine which was quite innovative. It contains a row of numbers, 'MoneyRow. Each time a player plays, the machine generates some random pairs of integers a and b. All such pairs are shown to the player who then has one chance to reorder the numbers of the MoneyRow.
After he is done with the rearranging and presses start button, money equal to the sum of the numbers from ath cell to bth cell ( both inclusive ) of the MoneyRow is added in his account.This process is repeated for each pair (but with the same arrangement of the MoneyRow) generated by the machine and the money in the account keeps on increasing.
Given the row and all pairs, you have to predict the maximum money he can win.
The first line contains T, the number of test cases. The next line contains two space separated integers n and q : the count of Numbers in the row and the number of pairs,respectively.
The next line contains n space separated integers Ni, The numbers in the row.
Each of the following q lines contain two space separated integers a and b representing the pair.
In a single line print a single integer : Maximum amount of money he can win.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 10^6
- 1 ≤ a ≤ b ≤ n
- 1 ≤ Ni ≤ 10^6
- 1 ≤ q ≤ 10^6
Input: 1 5 3 1 2 3 4 5 3 4 3 4 1 5 Output: 33
|Time Limit:||0.115 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions