**Problem Link:**

Contest

Practice

**Author:** Rajat De

**Editorialist:** Sidhant Bansal

**Difficulty:** Easy

**Pre-requisites:** Sorting

**Quick Explanation:**

Sort all the subjects in descending order according to C[i] and then greedily spend the hours on each of the subject turn by turn till the time the average does not come upto M.

**Explanation:**

For the average to be at least M, the total of all the marks should be at least M*N

If \sum A[i] \geq M*N then answer is 0.

Otherwise, calculate delta = (M*N) - \sum A[i]

Now, the original question reduces to studying least amount of hours so as to gain delta marks.

For calculating this, follow the below pseudocode -

Sort all subjects in descending order according to C[i]

Set answer = 0

For i = 1 to N

If B[i] - A[i] \geq delta

answer = answer + ceil(delta/C[i])

break

Else

answer = answer + (B[i] - A[i])/C[i]

delta = delta - (B[i] - A[i])

Print answer

**Complexity:** Time complexity is O(N * logN) and memory complexity is O(N)

The alternate solution is binary search on answer along with min cost max flow, please refer to the author solution for more details.