Training Site
Sideways banner


Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.5 seconds

It's about time that you show everyone your prowess at throwing pinecones.

You have collected N pinecones from the NZOI camp, and the ith pinecone can initally be thrown to a height of H_i meters. However, pinecones will weaken after each throw (since you aren't very good at catching them). Therefore, when throwing a pinecone again, it can only be thrown 1 meter lower than on its previous throw. When the height that a pinecone can be thrown to becomes 0, it breaks completely and cannot be thrown again. For example, if a pinecone can initially be thrown to a height of two meters, then the second time you throw this pinecone it can only reach a height of one meter. After this second throw the pinecone breaks.

Since you have a naturally inquisitive mind, you have imagined Q scenarios. For the jth scenario, you would like to know the maximum possible combined height (in meters) of your throws if you are allowed at most T_j throws in total. For each throw, you can use any pinecone that isn't completely broken. If all the pinecones are completely broken, you cannot perform any more throws.

Because all these scenarios are in your imagination, the height that each pinecone can be thrown resets to their initial height after each scenario.

Since the answer may be very large, for each scenario you should output the answer modulo 1{,}000{,}000{,}007 (remainder after dividing the answer by 1{,}000{,}000{,}007, which can be found with x % 1000000007 in most languages).

Note: If you're using a type-sensitive language such as C, C++, C# or Java, you should use 64-bit integer types to prevent integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.


  • The first line contains two space-separated integers, N and Q — the number of pinecones you have and the number of scenarios you have imagined.
  • The second line contains a list of space-separated integers, H_1, H_2, ..., H_n — the heights at which the pinecones you collected can be initially thrown, in meters.
  • For the next Q lines, the jth of these lines contains a single integer, T_j.


  • You should output Q lines. The jth of these lines should contain a single integer describing the maximum possible combined height after T_j throws, modulo 1{,}000{,}000{,}007.


  • 1 \leq N,Q \leq 10^5
  • 1 \leq H_i \leq 10^9 for all 1 \leq i \leq N
  • 1 \leq T_j \leq 10^{12} for all 1 \leq j \leq Q


  • Subtask 1 (+15%): Q = 1 and N \leq 1{,}000 and H_i \leq 1{,}000 for all 1 \leq i \leq N and T_j \leq 1{,}000 for all 1 \leq j \leq Q
  • Subtask 2 (+25%): Q = 1 and H_i \leq 10^5 for all 1 \leq i \leq N and T_j \leq 10^5 for all 1 \leq j \leq Q
  • Subtask 3 (+30%): H_i \leq 10^5 for all 1 \leq i \leq N
  • Subtask 4 (+30%): No further constraints

Sample Explanation

Note that in all scenarios in both samples, the answer modulo 1,000,000,007 is the same as itself.

  • Sample 1: In the 1st scenario, you can throw the second pinecone 1 time for 4 meters and the third pinecone 1 time for 5 meters, giving the maximum possible combined height of 9 meters. In the 2nd scenario, you can throw the first pinecone 1 time for 2 meters, the second pinecone 3 times for 4+3+2=9 meters, the third pinecone 4 times for 5+4+3+2=14 meters, and the fourth pinecone 2 times for 4+3=7 meters, giving a combined height of 32 meters. In the 3rd scenario, you can throw the second pinecone 2 times, the third pinecone 3 times, and the fourth pinecone 1 time for a combined height of 23 meters.

  • Sample 2: You can throw up to 10 times in the 1st (and only) scenario, but every pinecone will have broken completely before that. Therefore, by throwing every pinecone until it breaks, you can achieve the maximum possible combined height of 1+(2+1)+1=5 meters.


If you are using Python, select Python 3.6 (PyPy 7.3) among the language options when making a submission. Otherwise, your solution may not pass the time limit for some subtasks even if it is maximally efficient.

  • Sample Input 1

    4 3
    2 4 5 4

    Sample Output 1

  • Sample Input 2

    3 1
    1 2 1

    Sample Output 2