#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, m; pair <int, int> a[N]; namespace sub2 { /// 1 2 3 /// (1 - 2) + (2 - 3) + (3 - 1) /// 2 - 1 + 3 - 2 + 3 - 1 long long dp[2005][2005]; void solve () { memset(dp, - 0x3f, sizeof dp); for (int i = 1; i <= n; i++) { dp[i][1] = a[i].first + 1LL * 2 * a[i].second; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); if (j < m) { dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1].first - (j + 1 == m ? 1LL * 2 * a[i + 1].second : 0)); } } } long long ans = - 1e18; for (int i = m; i <= n; i++) { ans = max(ans, dp[i][m]); } cout << ans; } } namespace sub3 { void solve () { } } int32_t main () { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("kieuoanh.inp", "r", stdin); // freopen("kieuoanh.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second; sort (a + 1, a + 1 + n, [&] (pair <int, int> u, pair <int, int> v) { return u.second < v.second; }); /// for (int i = 1; i <= n; i++) cout << a[i].first << " " << a[i].second << "\n"; if (n <= 2000) return sub2::solve(), 0; return sub3::solve(), 0; return 0; }