#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
using namespace std;
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  long long n, k;
  cin >> n >> k;
  vector<bool> dp(k);
  dp[0] = true;
  long long sum = 0;
  for (long long i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    sum += a + b;
    vector<long long> v = {a};
    for (long long j = 0; j <= k; j++) {
      long long na = a - j, nb = b - (k - j);
      if (na >= 0 && nb >= 0) v.push_back(na);
    }
    vector<bool> tmp(k);
    for (long long j = 0; j < k; j++) {
      if (dp[j])
        for (long long x : v) tmp[(j + x) % k] = true;
    }
    dp = tmp;
  }
  long long ans = 0;
  for (long long i = 0; i < k; i++) {
    if (!dp[i]) continue;
    ans = max(ans, (sum - i - ((sum - i) % k)) / k);
  }
  cout << ans << "\n";
}
