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 $⌈\frac{p}{q}⌉$. 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 $n \le 10^3, t \le 10^4$. - The second line contains $n$ positive integers $a_1, a_2, ..., a_n$ representing the number of people in each group $(a_i \le 10^4)$. - The next $t$ lines, each containing a positive integer $m$, represent scenarios with $m$ nurses participating in the vaccination $(n \le m \le 10^4)$. ### 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 $n \le 7; t\le10;a_i\le10$. - 20% of tests have $n \le 60;a_i \le 1000$. - 20% of tests have $n \le 300;a_i \le 1000$. - 20% of tests have $n \le 1000;a_i\le1000$. - 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 ```