#include <bits/stdc++.h>
using namespace std;
long long int mod = 67280421310721;
long long int INF = 1e18;
long long int po(long long int a, long long int b) {
  long long int re = 1;
  while (b) {
    if (b % 2 == 1) {
      re = (re * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return re;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test = 1;
  while (test--) {
    int n, k;
    cin >> n >> k;
    long long int a[n], b[n], sa = 0, sb = 0;
    for (long long int i = (0); i < (n); i++) {
      cin >> a[i] >> b[i];
      sa += a[i];
      sb += b[i];
    }
    int ra = sa % k, rb = sb % k;
    if ((ra + rb) < k) {
      cout << (sa + sb) / k;
      return 0;
    }
    bitset<505> pa = 0, tem = 0;
    bool rtem;
    pa[ra] = 1;
    for (long long int i = (0); i < (n); i++) {
      if ((a[i] + b[i]) >= k) {
        tem = pa;
        for (long long int j = (1); j < (k); j++) {
          rtem = tem[0];
          tem >>= 1;
          tem[k - 1] = rtem;
          if ((a[i] >= j) && (b[i] >= (k - j))) {
            pa = pa | tem;
          }
        }
      }
    }
    int h = ra + rb - k;
    bool ans = 0;
    for (long long int i = (0); i < (h + 1); i++) {
      if (pa[i] == 1) ans = 1;
    }
    if (ans) {
      cout << (sa + sb) / k;
    } else {
      cout << ((sa + sb) / k) - 1;
    }
  }
  return 0;
}
