#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const double pi = 3.1415926535897932, eps = 1e-6;
void chmax(int &x, int y) {
  if (x < y) x = y;
}
void chmin(int &x, int y) {
  if (x > y) x = y;
}
long long n, a[505], b[505], k, sa, sb, ans;
bitset<1010> g[505], e, ne;
long long f(long long x) {
  if (x < k) return x;
  return k + x % k;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  for (int(i) = (1); (i) <= (n); (i)++) cin >> a[i] >> b[i];
  for (int(i) = (1); (i) <= (n); (i)++) sa += a[i], sb += b[i];
  ans = sa / k + sb / k;
  if ((sa % k + sb % k) < k) {
    cout << ans << endl;
    return 0;
  }
  for (int(i) = (1); (i) <= (n); (i)++) {
    a[i] = f(a[i]);
    b[i] = f(b[i]);
    long long sum = a[i] + b[i];
    if (sum < k) {
      g[i][a[i] % k] = 1;
    } else {
      g[i][a[i] % k] = 1;
      int lim = min(min(sum - k, k), a[i]);
      for (int(j) = (max(0ll, lim - b[i])); (j) <= (lim); (j)++) {
        g[i][j % k] = 1;
      }
    }
  }
  e = g[1];
  for (int(i) = (2); (i) <= (n); (i)++) {
    ne = 0;
    for (int(j) = (0); (j) < (k); (j)++)
      if (e[j]) {
        ne |= g[i] << j;
      }
    e = 0;
    for (int(j) = (0); (j) < (2 * k); (j)++) {
      if (ne[j]) e[j % k] = 1;
    }
  }
  long long rem = (sa + sb) % k;
  for (int(j) = (0); (j) < (k); (j)++)
    if (j <= rem && e[j]) {
      ans++;
      break;
    }
  cout << ans << endl;
  return 0;
}
