#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, k, a[N], b[N];
bool dp[N], tmp[N];
long long suma, sumb;
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], suma += a[i], sumb += b[i];
  int ya = suma % k, yb = sumb % k;
  if (ya + yb < k) {
    cout << suma / k + sumb / k << endl;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < k; j++) tmp[j] = dp[j];
    for (int j = 0; j < k; j++) {
      for (int x = 1; x < k; x++)
        if (x <= a[i] && k - x <= b[i]) {
          dp[(j + x) % k] |= tmp[j], dp[x] = 1;
        }
    }
  }
  long long ans = suma / k + sumb / k;
  for (int i = 1; i < k; i++)
    if (i <= ya && k - i <= yb && dp[i]) {
      ans++;
      break;
    }
  cout << ans << endl;
  return 0;
}
