Description: The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 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... Input Format: Same as the medium version, but the limits have changed: 1 ≤ k ≤ n ≤ 500 000. Output Format: Same as the medium version. Note: None