Admins and Shopping Solution | CodeChef Problem Solution 2022

Admins and Shopping Solution | CodeChef Problem Solution 2022

CodeChef admins went on shopping at a shopping mall.

There are N$N$ shops in the mall where the ith$i^{th}$ shop has a capacity of Ai$A_i$ people. In other words, at any point in time, there can be at most Ai$A_i$ number of people in the ith$i^{th}$ shop.

There are X$X$ admins. Each admin wants to visit each of the N$N$ shops exactly once. It is known that an admin takes exactly one hour for shopping at any particular shop. Find the minimum time (in hours) in which all the admins can complete their shopping.

Note:

1. An admin can visit the shops in any order.
2. It is possible that at some point in time, an admin sits idle and does not visit any shop while others are shopping.

Input Format

• First line will contain T$T$, the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers N$N$ and X$X$ - the number of shops and the number of admins.
• The second line of each test case contains N$N$ integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ - the capacity of the shops.

Output Format

For each test case, output in a single line the minimum time (in hours) in which all the admins can complete their shopping.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤X,Ai≤109$1\le X,A_i\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

3
2 3
3 3
4 2
1 2 3 4
1 6
2

Sample Output 1 

2
4
3

Explanation

Test case 1$1$: Minimum time required to complete the shopping is two hours. A possible way to complete shopping in 2$2$ hours is :

• 1st$1^{st}$ hour: All 3$3$ admins visit shop 1$1$. This is possible as the capacity of the shop is 3≥3$3\ge 3$.
• 2nd$2^{nd}$ hour: All 3$3$ admins visit shop 2$2$. This is possible as the capacity of the shop is 3≥3$3\ge 3$.

Test case 2$2$: Minimum time required to complete the shopping is 4$4$ hours. A possible way to complete shopping in 4$4$ hours is :

• 1st$1^{st}$ hour: Admin 1$1$ visits shop 1$1$ and admin 2$2$ visits shop 4$4$.
• 2nd$2^{nd}$ hour: Admin 1$1$ visits shop 2$2$ and admin 2$2$ visits shop 3$3$.
• 3rd$3^{rd}$ hour: Admin 1$1$ visits shop 3$3$ and admin 2$2$ visits shop 2$2$.
• 4th$4^{th}$ hour: Admin 1$1$ visits shop 4$4$ and admin 2$2$ visits shop 1$1$.

Test case 3$3$: Minimum time required to complete the shopping is 3$3$ hours. A possible way to complete shopping in 3$3$ hours is :

• 1st$1^{st}$ hour: Admins 1$1$ and 2$2$ visits shop 1$1$. All other admins sit idle.
• 2nd$2^{nd}$ hour: Admins 3$3$ and 4$4$ visits shop 1$1$. All other admins sit idle.
• 3rd$3^{rd}$ hour: Admins 5$5$ and 6$6$ visits shop 1$1$. All other admins sit idle.
  Note that, since the capacity of shop is 2$2$, maximum 2$2$ admins visit the shop at once.