#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
const int N = 1 << 9;
const ll inf = 1e18;
bool dp[N][N];
int rem[N][N], n, k, a[N], b[N];
int sub(int a, int b) {
  int t = a - b;
  return t < 0 ? t + k : t;
}
int add(int a, int b) {
  int t = a + b;
  return k <= t ? t - k : t;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  ll tot = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    tot += a[i] + b[i];
  }
  dp[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (auto j = (0); j < (k); ++j) {
      rem[i][j] = k - 1;
      for (auto l = (0); l < (min(k, a[i] + 1)); ++l) {
        if (a[i] % k == l || k <= (a[i] - l) % k + b[i]) {
          if (dp[i - 1][sub(j, l)]) {
            dp[i][j] = true;
            ckmin(rem[i][j], (rem[i - 1][sub(j, l)] + b[i] + a[i] - l) % k);
          }
        }
      }
    }
  }
  ll ans = 0;
  for (auto j = (0); j < (k); ++j)
    if (dp[n][j]) ckmax(ans, (tot - j - rem[n][j]) / k);
  cout << ans;
}
