A friend talked me about this problem and i don't know how to solve it or if there is a judge to make submitions.

You will be given an array of $$$N$$$ integers $$$A$$$. You know that $$$ 1 \leq N \leq 2000$$$ and $$$1 \leq A_i \leq 10^6$$$.

Is there any way to know for a fixed $$$1 \leq k \leq N$$$ the maximum number of times you can choose $$$k$$$ different elements from $$$A$$$ with the condition that if you choose indexes $$$p_1,p_2,...,p_k$$$ then you have to do $$$A_{p_i}-=1$$$ for every $$$1 \leq i \leq k$$$ and $$$A_i \geq 0$$$ should hold.

My idea is that every time, you have to choose the currently $$$k$$$ greatest elements (but i don´t know if this is optimal, i did´nt prove it). And i guess that the time complexity for this would be $$$O( $$$$$$\sum_{i=1}^{n} A_i $$$$$$ ) \approx 10^9 $$$ worst case.

Another version

You are free to choose $$$k$$$ in such a way that at the end of the process with that $$$k$$$ (the process described above) the sum of the remaining elements should be minimum. You have to find the greatest $$$k$$$ meet this condition.

Any comment is welcome. Thank you.