#include <bits/stdc++.h>
using namespace std;
vector<int> pyramids;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> v(n);
  vector<long long> pref(n);
  long long summe = 0;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  for (int i = 0; i < n; i++) {
    summe += v[i].first + v[i].second;
    pref[i] = summe;
  }
  vector<vector<bool>> possible(n, vector<bool>(k, false));
  for (int i = 0; i < n; i++) {
    if (i == 0) {
      possible[i][v[i].first % k] = true;
      for (int take_red = 1; take_red < k; take_red++) {
        int take_blue = k - take_red;
        if (take_red <= v[i].first && take_blue <= v[i].second) {
          possible[i][(v[i].first - take_red) % k] = true;
        }
      }
    } else {
      for (int over_flow_red = 0; over_flow_red < k; over_flow_red++) {
        if (possible[i - 1][over_flow_red]) {
          possible[i][(over_flow_red + v[i].first) % k] = true;
          for (int take_red = 1; take_red < k; take_red++) {
            int take_blue = k - take_red;
            if (take_red <= v[i].first && take_blue <= v[i].second) {
              possible[i][(v[i].first - take_red + over_flow_red) % k] = true;
            }
          }
        }
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < k; i++) {
    if (possible[n - 1][i]) {
      ans = max(ans, (pref[n - 1] - i) / k);
    }
  }
  cout << ans << '\n';
}
