#include <bits/stdc++.h>
using namespace std;
long long n, k, a = 0, b = 0;
vector<pair<long long, long long>> v;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  v.assign(n, {-1, -1});
  for (int i = 0; i < n; ++i) {
    cin >> v[i].first >> v[i].second;
    a += v[i].first;
    b += v[i].second;
  }
  long long rem = (a % k) + (b % k);
  if (rem < k) {
    cout << a / k + b / k;
    return 0;
  }
  bool poss = false;
  long long ra = a % k, rb = b % k;
  long long diffA = (ra - rb + k) % k;
  vector<vector<bool>> adj(n, vector<bool>(k, 0));
  vector<vector<bool>> dp(n + 1, vector<bool>(k, 0));
  for (int i = 0; i < n; ++i) {
    adj[i][0] = true;
    for (int j = 1; j < k; ++j) {
      if (v[i].first >= j && v[i].second >= k - j) {
        adj[i][j] = true;
      }
    }
  }
  dp[0][0] = true;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) {
      for (int x = 0; x < k; ++x) {
        if (!dp[i][x]) continue;
        if (!adj[i][j]) continue;
        dp[i + 1][(x + j) % k] = true;
      }
    }
  }
  long long res = a / k + b / k;
  for (int j = 0; j < k; ++j) {
    if (dp[n][j]) res = max(res, (a - j) / k + (b + j) / k);
  }
  cout << res;
  return 0;
}
