#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long INF = (long long)1000000007 * 1000000007;
const long double eps = 1e-8;
const long double pi = acos(-1.0);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, k;
long long a[510], b[510];
bool dp[510][510];
void solve() {
  cin >> n >> k;
  long long p = 0, q = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    p += a[i];
    q += b[i];
  }
  if ((p % k + q % k) / k == 0) {
    cout << p / k + q / k << endl;
    return;
  }
  dp[0][0] = true;
  for (int i = 0; i < n; i++) {
    for (int s = 0; s < k; s++) {
      for (int j = 0; j < k; j++) {
        if (dp[i][j]) {
          dp[i + 1][j] = true;
          if (a[i] < s || b[i] < k - s) continue;
          dp[i + 1][(j + s) % k] = true;
        }
      }
    }
  }
  bool f = false;
  for (int t = k - q % k; t < p % k + 1; t++) {
    if (dp[n][t]) f = true;
  }
  cout << p / k + q / k + f << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(50);
  solve();
}
