#include <bits/stdc++.h>
using namespace std;
long long a[505], b[505];
int dp[505][505];
int main() {
  ios_base::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  long long tA = 0, tB = 0, tot = 0;
  long long ra, rb;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    tA += a[i];
    tB += b[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      if (i == 0) {
        dp[i][0] = 1;
        if (j <= a[i] && j >= k - b[i])
          dp[i][j] = 1;
        else
          dp[i][j] = max(dp[i][j], 0);
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j]);
        for (long long ax = max((long long)0, k - b[i]);
             ax <= min(a[i], (long long)k - 1); ax++) {
          dp[i][(j + ax) % k] = max(dp[i][(j + ax) % k], dp[i - 1][j]);
        }
      }
    }
  }
  for (int i = 0; i < k; i++) {
    if (dp[n - 1][i] == 1) {
      long long val =
          (tA - i) / k + (tB - ((k - i) % k)) / k + ((i == 0) ? 0 : 1);
      tot = max(tot, val);
    }
  }
  cout << tot << endl;
}
