Processing math: 100%
Vaccination - MarisaOJ: Marisa Online Judge

Vaccination

Time limit: 1000 ms
Memory limit: 256 MB

An epidemic is seriously affecting people’s lives, prompting the city to organize a vaccination campaign across the entire area. Based on addresses, the Centers for Disease Control (CDC) divides the individuals into n groups and mobilizes m nurses to carry out vaccinations at the city’s largest hospital. Because the epidemic spreads rapidly, the infection control process in the vaccination area must adhere to a strict procedure as follows:

  • Each nurse will participate in vaccinating one group and only one group.
  • Nurses working together on a group will work simultaneously, taking exactly 1 minute to vaccinate each person.
  • This means that if a group of p people is vaccinated by q nurses, the vaccination time for the entire group will be pq. For example, if a group of 30 people is vaccinated by 4 nurses, the group will complete the vaccination in 8 minutes, but if vaccinated by 5 nurses, it will only take 6 minutes.

Upon completing the vaccination, each group must leave immediately for the next group to begin vaccination.

Requirements: You are given the number of groups n, the number of people in each group, and the number of nurses m. Find a way to assign each nurse to a group to minimize the total vaccination time for the n groups.

Since during the epidemic, nurses can be suddenly reassigned, you need to plan for t scenarios, each scenario specified by the number of nurses who can participate in the vaccination (m).

Input

  • The first line consists of two positive integers n103,t104.
  • The second line contains n positive integers a1,a2,,an representing the number of people in each group (ai104).
  • The next t lines, each containing a positive integer m, represent scenarios with m nurses participating in the vaccination (nm104).

Output

  • Print t lines, where the i-th line is the total vaccination time for the i-th scenario, measured in minutes.

Constraints

  • 20% of tests have n7;t10;ai10.
  • 20% of tests have n60;ai1000.
  • 20% of tests have n300;ai1000.
  • 20% of tests have n1000;ai1000.
  • The remaining 20% of tests have no additional constraints.

Example

Input:

3 4
6 10 1
3
9
12
4

Output:

17
5
4
12