Hide

Languages

Raunak and his friends want to play a prank on their neighbors by performing the classic "Ding Dong Ditch". They want to individually ring the doorbell of a number of their neighbors and then run away from there. But some neighbors are very dangerous, since they could get very angry and even potentially bite you!

There are $N$ neighbors that live on their street. For each neighbor $i$, the neighbor has a value $A_ i$ that represents how angry they become when their doorbell is rung. Raunak has $Q$ friends, including himself. For each friend $j$ they have a specific level of ambition $B_ j$, which represents the number of houses they can ring the doorbell on before chickening out.

For each friend who rings the doorbell, they want to choose $B_ j$ different houses that minimizes the sum of the anger values $A_ i$ of all of those houses. Help Raunak figure out the smallest possible sum of anger values that each friend can achieve!

Note that multiple friends may ring the doorbell of the same house.

## Input

The first line consists of two positive integers $N, Q$ ($1 \leqslant N \leqslant 2 \cdot 10^5$, $1 \leqslant Q \leqslant 10^5$), the number of houses in the neighborhood and the number of friends that Raunak has, respectively. The next line consists of $N$ distinct positive integers separated by spaces, where each integer $1 \leqslant A_ i \leqslant 10^9$ represents the anger value of each neighbor. The last line consists of $Q$ positive integers separated by spaces, where each integer $1 \leqslant B_ j \leqslant N$ represents how many houses that friend $j$ can ring the doorbell of.

## Output

Print $Q$ lines, where each line consists of an integer - The smallest sum of anger value that friend $j$ can achieve by ringing $B_ j$ doorbells.

Your solution will be tested on a number of test-case groups. To receive points for a group, your solution must correctly solve every test-case in the group.

 Group Point value Constraints $1$ $10$ $Q=1, N \leqslant 10$ $2$ $25$ $Q\leqslant 10^3, N \leqslant 100$ $3$ $10$ All $B_ j$ are either $1$ or $N$. $4$ $20$ $Q\leqslant 10^3, N \leqslant 10^4$ $5$ $35$ No further restrictions
Sample Input 1 Sample Output 1
4 2
3 2 1 4
3 1

6
1

Sample Input 2 Sample Output 2
5 1
12 2 14 6 9
3

17

Hide