이기적인 목봉 체조 (Hard)

이 문제는 이기적인 목봉 체조 (Easy) 문제와 $N$ 제한 및 시간 제한을 제외하고 같은 문제이다.

대망의 유격 훈련 날, 조교는 훈련병들에게 목봉 체조 훈련을 시키려고 한다. 목봉 체조 훈련이란 여러 명이 동시에 하나의 목봉을 어깨높이로 들고, 반대편 어깨로 목봉을 옮기는 훈련이다.

조교들은 $N$명의 모든 훈련병들을 $M$개의 그룹으로 나눠서 목봉 체조를 실시하고자 한다. 이때, 훈련병들의 번호를 헷갈리지 않도록 서 있는 순서대로 연속된 훈련병들만 한 그룹으로 묶어야 하며, 각 그룹은 한 명 이상의 훈련병들로 구성되어야 한다.

하지만 이 훈련병들은 전부 다 너무 이기적이어서, 동일한 그룹에 본인보다 키가 조금이라도 큰 훈련병이 있다면 힘을 아예 쓰지 않고 드는 척만 한다. 즉, 그룹 안에서 키가 가장 큰 훈련병들만 목봉에 힘을 가한다.

$N$명의 훈련병을 적절히 $M$개의 그룹으로 나누었을 때 훈련병들이 들 수 있는 목봉 무게의 합의 최댓값을 구하여라.

첫 번째 줄에 훈련병의 수 $N$과 그룹의 수 $M$이 공백으로 구분되어 주어진다. $(1\leq N\leq 100\\,000;$ $1\leq M\leq 10;$ $M\leq N)$

두 번째 줄부터 $N+1$번째 줄까지, 훈련병의 키를 나타내는 정수 $h\_i$와 힘을 나타내는 정수 $s\_i$가 서 있는 순서대로 공백으로 구분되어 주어진다. $(1\leq h\_i, s\_i\leq 10^9)$

$N$명의 훈련병을 적절히 $M$개의 그룹으로 나누었을 때 훈련병들이 들 수 있는 목봉 무게 합의 최댓값을 출력한다.