Luogu_P_8816.cpp

#include <bits/extc++.h>
using namespace std;
namespace pbds = __gnu_pbds;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
struct pos {
  ui x, y;
  friend bool operator<(pos const& a, pos const& b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
  }
  friend istream& operator>>(istream& in, pos& x) { return in >> x.x >> x.y; }
  static ui dist(pos const& a, pos const& b) {
    return (max(a.x, b.x) - min(a.x, b.x)) + (max(a.y, b.y) - min(a.y, b.y));
  }
};
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t n, k;
  cin >> n >> k;
  vector<pos> a(n);
  for (pos& i : a) cin >> i;
  sort(a.begin(), a.end());
  vector<vector<size_t>> dp(n, vector<size_t>(k + 1));
  size_t ans = 0;
  for (size_t i = 0; i < n; i++) {
    dp[i][0] = 1;
    for (size_t j = 0; j < i; j++)
      if (a[i].x >= a[j].x && a[i].y >= a[j].y) {
        ui dis = pos::dist(a[i], a[j]) - 1;
        for (size_t x = dis; x <= k; x++)
          if (dp[j][x - dis])
            dp[i][x] = max(dp[j][x - dis] + dis + 1, dp[i][x]);
      }
  }
  for (vector<size_t> const& i : dp)
    for (size_t j = 0; j <= k; j++) ans = max(ans, i[j] + k - j);
  cout << ans;
  return 0;
}