#include <bits/stdc++.h>
using namespace std;
pair<bool, bool> dp[500][500];
pair<int, int> arr[500];
int k;
bool possibility(int index, int rem) {
  if (index < 0) return (rem == 0);
  if (dp[index][rem].second) {
    return dp[index][rem].first;
  }
  dp[index][rem].second = true;
  dp[index][rem].first = (rem == 0);
  dp[index][rem].first = dp[index][rem].first || possibility(index - 1, rem);
  int i;
  for (i = max(1, k - arr[index].second); i < k && i <= arr[index].first; i++) {
    dp[index][rem].first =
        dp[index][rem].first || possibility(index - 1, (k + rem - i) % k);
  }
  return dp[index][rem].first;
}
int main() {
  long long ans = 0;
  int n, i, j;
  scanf("%d %d", &n, &k);
  pair<long long, long long> sum;
  sum.first = sum.second = 0;
  for (i = 0; i < n; i++) {
    scanf("%d %d", &arr[i].first, &arr[i].second);
    sum.first = sum.first + arr[i].first;
    sum.second = sum.second + arr[i].second;
  }
  ans = ans + (sum.first / k);
  ans = ans + (sum.second / k);
  sum.first = sum.first % k;
  sum.second = sum.second % k;
  if (sum.first + sum.second < k) {
    printf("%I64d", ans);
    return 0;
  }
  pair<int, int> p;
  p.first = (int)sum.first;
  p.second = (int)sum.second;
  bool possible = false;
  for (i = max(1, k - p.second); i <= p.first; i++) {
    possible = possible || possibility(n - 1, i);
  }
  ans = ans + possible;
  printf("%I64d", ans);
  return 0;
}
