The plans for HC² are rather far-fetched: we are just over 500 000 days away from HC² 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...

Same as the medium version, but the limits have changed: 1≤k≤n≤500000.

Same as the medium version.