#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
const int N=2e5+5;
int lowbit(int x){
	return x&-x;
}
int n,m,c[N],v[N];
long long dp[2][N],tr[N],trev[N];//dp[i][j]:一共保留j个 最后一个保留的是j
void add(int x,long long c,int opt){
	if(opt==2){//trev
		x=n-x+1;
		for(int i=x;i<=n;i+=lowbit(i)){
			trev[i]=max(trev[i],c);
		}
	}
	else{
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]=max(tr[i],c);
		}
	}
}
long long query(int x,int opt){
	long long ret=-1e18;
	if(opt==2){
		x=n-x+1;
		while(x){
			ret=max(ret,trev[x]),x-=lowbit(x);
		}
	}
	else{
		while(x){
			ret=max(ret,tr[x]),x-=lowbit(x);
		}
	}
	return ret;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m,m=n-m;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>v[i];
	}
	memset(dp,128,sizeof(dp));
	for(int i=1;i<=n;i++){
		dp[1][i]=v[i];
	}
	for(int i=2;i<=m;i++){
		for(int j=1;j<=n;j++){
			tr[j]=trev[j]=-1e18;
		}
		for(int j=1;j<=n;j++){//当j>=2 插入dp[(i-1)%2][j-1]
		    if(j>=2){
		    	add(c[j-1],dp[(i-1)%2][j-1],1),add(c[j-1],dp[(i-1)%2][j-1],2);
			}
			dp[i%2][j]=max(query(c[j]-1,1),query(c[j]+1,2))+v[j];
		}
	}
	long long ans=dp[m%2][1];
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[m%2][i]);
	}
	if(ans<0){
		cout<<-1;
	}
	else{
		cout<<ans;
	}
}