#include <bits/stdc++.h>
using namespace std;
bool dp[501][501];
long long a[501], b[501];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  long long sumr = 0, sumb = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    sumr += a[i], sumb += b[i];
  }
  dp[sumr % k][sumb % k] = true;
  int sum = (sumr + sumb) % k;
  bool rc = false;
  if ((sumr % k) + (sumb % k) < k) rc = true;
  for (int i = 1; i <= n; i++) {
    for (int j1 = 1; j1 < k; j1++) {
      if (a[i] >= j1 && b[i] >= k - j1) {
        vector<pair<int, int> > sav;
        for (int j2 = 0; j2 < k; j2++) {
          int l = (sum + j2) % k, r = k - j2;
          if (dp[l][r]) {
            l = (l + k - j1) % k;
            r = (r + j1) % k;
            sav.push_back({l, r});
            if (l + r < k) {
              rc = true;
              j2 = k, j1 = k, i = n + 1;
            }
          }
        }
        for (auto v : sav) dp[v.first][v.second] = true;
      }
    }
  }
  if (rc)
    cout << (sumr + sumb) / k << endl;
  else
    cout << max((sumr + sumb) / k - 1, 0 * 1ll) << endl;
}
