2022B.md (1976B)
1 Source: https://codeforces.com/problemset/problem/2022/B 2 3 B. Kar Salesman 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Karel is a salesman in a car dealership. The dealership has $n$ different models of cars. There are $a_i$ cars of the $i$-th model. Karel is an excellent salesperson and can convince customers to buy up to $x$ cars (of Karel's choice), as long as the cars are from different models. 22 23 Determine the minimum number of customers Karel has to bring in to sell all the cars. 24 25 Input 26 27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 28 29 The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 5 \cdot 10^5$; $1 \le x \le 10$) — the number of different models of cars and the maximum number of cars Karel can convince a customer to buy. 30 31 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number of cars of each model. 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$. 34 35 Output 36 37 For each test case, output the minimum possible number of customers needed to sell all the cars. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 46 3 2 47 48 3 1 2 49 50 3 3 51 52 2 1 3 53 54 5 3 55 56 2 2 1 9 2 57 58 7 4 59 60 2 5 3 3 5 2 5 61 ``` 62 63 Output 64 65 ``` 66 3 67 3 68 9 69 7 70 ``` 71 72 Note 73 74 For the first case, Karel only needs to lure in $3$ customers. He will convince the customers to buy the following models of cars: 75 76 * Customer $1$ buys $2$ cars with model $1$ and $3$. 77 * Customer $2$ buys $2$ cars with model $1$ and $2$. 78 * Customer $3$ buys $2$ cars with model $1$ and $3$. 79 80 For the second case, Karel only needs to lure in $3$ customers. He will convince the customers to buy the following models of cars: 81 82 * Customer $1$ buys $2$ cars with model $1$ and $3$. 83 * Customer $2$ buys $3$ cars with model $1$, $2$ and $3$. 84 * Customer $3$ buys $1$ car with model $3$.