#include <iostream>
#include <algorithm>
using namespace std;

#define x first
#define y second

int n, k, ans;
pair<int, int> a[505];
int f[505][105];

int main() {
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i++) cin >> a[i].x >> a[i].y;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 0 ; j <= k ; j++)
            f[i][j] = j + 1;
    sort(a + 1, a + n + 1);
    for (int i = 1 ; i <= n ; i++) {
        for (int j = i - 1 ; j >= 1 ; j--) if (a[j].y < a[i].y) {
            int d = a[i].x - a[j].x + a[i].y - a[j].y - 1;
            for (int p = d ; p <= k ; p++)
                f[i][p] = max(f[i][p], f[j][p - d] + d + 1);
        }
        ans = max(ans, f[i][k]);
    }
    cout << ans;
    return 0;
}