#include <bits/stdc++.h>
using namespace std;
bool dp[505][505];
int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N + 1), b(N + 1);
  long long sumA = 0, sumB = 0;
  for (int i = 1; i <= N; i++) {
    cin >> a[i] >> b[i];
    sumA += a[i];
    sumB += b[i];
  }
  dp[0][0] = true;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < K; j++) {
      for (int l = 0; l <= min(K - 1, a[i]); l++) {
        int need_b = (K - ((a[i] - l) % K)) % K;
        if (need_b > b[i]) {
          continue;
        }
        if (dp[i - 1][j]) {
          dp[i][(j + l) % K] = true;
        }
      }
    }
  }
  long long ans = 0;
  for (int x = 0; x < K; x++) {
    if (dp[N][x]) {
      ans = max(ans, (sumA + sumB - x) / K);
    }
  }
  cout << ans << endl;
  return 0;
}
