#include <bits/stdc++.h>
using namespace std;
const int N = 505;
long long dp[N][N];
int c[N][N], a[N], b[N], k, aa[N], bb[N];
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n >> k;
  auto fast_mod = [](int a) {
    if (a >= 2 * k) return a % k;
    if (a < 0) return a + k;
    return a >= k ? a - k : a;
  };
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    aa[i] = fast_mod(a[i]);
    bb[i] = fast_mod(b[i]);
  }
  memset(c, -1, sizeof c);
  queue<pair<int, int> > q;
  c[1][0] = 0;
  q.push({1, 0});
  while (q.size()) {
    int x, y, z;
    tie(x, y) = q.front();
    q.pop();
    z = c[x][y];
    for (int p = 1; p < k && p <= a[x]; p++)
      if (b[x] >= k - p && c[x + 1][fast_mod(aa[x] - p + y)] < 0) {
        c[x + 1][fast_mod(aa[x] - p + y)] = fast_mod(z + bb[x] - (k - p));
        q.push({x + 1, fast_mod(aa[x] - p + y)});
      }
    if (c[x + 1][fast_mod(y + aa[x])] < 0) {
      c[x + 1][fast_mod(y + aa[x])] = fast_mod(z + bb[x]);
      q.push({x + 1, fast_mod(y + aa[x])});
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < k; j++)
      if (~c[i][j]) {
        dp[i][j] = 1LL * (j + a[i]) / k + 1LL * (c[i][j] + b[i]) / k +
                   dp[i + 1][fast_mod(j + aa[i])];
        for (int p = 1; p < k && p <= a[i]; p++)
          if (b[i] >= k - p) {
            dp[i][j] = max(dp[i][j], 1LL + 1LL * (a[i] - p + j) / k +
                                         1LL * (b[i] - (k - p) + c[i][j]) / k +
                                         dp[i + 1][fast_mod(aa[i] - p + j)]);
          }
      }
  }
  cout << dp[1][0] << endl;
}
