#include <bits/stdc++.h>
using namespace std;
template <class C>
inline bool in_(const typename C::key_type& k, const C& A) {
  return A.find(k) != A.end();
}
inline bool in_(const string& s, const string& S) {
  return S.find(s) != string::npos;
}
const long long inf = 1e12;
const int maxn = 510;
int n, k, dp[maxn][maxn], A[maxn], B[maxn];
int dfs(const int i, const int j) {
  if (i == -1) return j == 0;
  int& ans = dp[i][j];
  if (-1 == ans) {
    ans = 0;
    for (int x = (0); x < (k); ++x) {
      const int y = k - x;
      long long a = A[i], b = B[i];
      if (x <= A[i] && y <= B[i]) a -= x, b -= y;
      int r = (j - a) % k;
      if (r < 0) r += k;
      ans |= dfs(i - 1, r);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  while (cin >> n >> k) {
    memset(dp, -1, sizeof(dp));
    long long rs = 0, bs = 0;
    for (int i = (0); i < (n); ++i) {
      cin >> A[i] >> B[i];
      rs += A[i];
      bs += B[i];
    }
    long long ans = 0;
    for (int r = (0); r < (k); ++r)
      if (dfs(n - 1, r)) ans = max(ans, (rs + bs - r) / k);
    cout << ans << endl;
  }
  return 0;
}
