#include <bits/stdc++.h>
using namespace std;
int n, k, i, a[505], b[505], j, l, dp[505][505];
long long ans1, ans2, ans;
int main() {
  cin >> n >> k;
  for (i = 1; i <= n; ++i) cin >> a[i] >> b[i], ans1 += a[i], ans2 += b[i];
  dp[0][0] = 1;
  for (i = 1; i <= n; ++i) {
    for (j = 0; j < k; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (!dp[i][j]) {
        for (l = 0; l < k; ++l) {
          if (a[i] >= (k + j - l) % k && b[i] >= k - ((k + j - l) % k))
            dp[i][j] |= dp[i - 1][l];
        }
      }
    }
  }
  ans = ans1 / k + ans2 / k;
  for (i = 0; i < k; ++i) {
    if (dp[n][i]) {
      ans = max(ans, (ans1 - i) / k + (ans2 + i) / k);
    }
  }
  cout << ans << "\n";
  return 0;
}
