https://www.codechef.com/LRNDSA04/problems/TRANSACT

I’ve been frying my head over it for two days and I can’t seem to wrap my head around the solution.

I’ve read the editorial but couldn’t understand all the Math.

I read about flow decomposition, Max flow min cut and I think i have a basic layman’s understanding of these (without all the proofs involved) but couldn’t move forward with this problem.

Can anyone, please, explain the basic idea behind solution in english with few sample inputs ? It will be great if anyone explains it using binary search.

I tried running a successful submission with different inputs but cannot understand the output.

For example - I ran it with input -

4 1

5 7 9 10

Answer is 7. How ? shouldn’t it be 8 ? Can’t all the other three elements can give one coin to 5 for total of 8 ?

Thank you.