#include <bits/stdc++.h>
using namespace std;
int N, K, a[600], b[600];
bool best[600][600];
long long A, B;
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; ++i) {
    cin >> a[i] >> b[i];
    A += a[i];
    B += b[i];
  }
  if (A % K + B % K < K) {
    cout << (A + B) / K << "\n";
    return 0;
  }
  int z = (A + B) % K;
  best[0][A % K] = 1;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < K; ++j) {
      best[i][j] = best[i - 1][j];
      for (int l = 0; l < K; ++l) {
        if (!best[i - 1][l]) continue;
        int fa = (l - j + K) % K;
        int fb = (K - fa) % K;
        if (fa <= a[i] && fb <= b[i]) {
          best[i][j] |= best[i - 1][l];
        }
      }
      if (best[i][j] && j <= z) {
        cout << (A + B) / K << "\n";
        return 0;
      }
    }
  }
  cout << (A / K + B / K) << "\n";
  return 0;
}
