#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
int a[MAXN], b[MAXN];
bool dp[MAXN][MAXN];
int main() {
  int n, k;
  while (scanf("%d%d", &n, &k) == 2) {
    long long ans = 0;
    long long sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &a[i], &b[i]);
      sum1 += a[i];
      sum2 += b[i];
    }
    ans = sum1 / k + sum2 / k;
    long long res = sum1 % k + sum2 % k;
    if (res < k) {
      cout << ans << endl;
      continue;
    }
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < k; j++) {
        if (dp[i - 1][j]) {
          dp[i][j] = true;
          for (int x = 1; x < k; x++) {
            if (a[i] >= x && b[i] >= k - x) {
              dp[i][(j + x) % k] = true;
            }
          }
        }
      }
    }
    bool flag = false;
    for (int i = 0; i <= sum1 % k; i++) {
      if (dp[n][i] && sum2 % k + i >= k) {
        flag = true;
        break;
      }
    }
    for (int i = 1; i <= sum2 % k; i++) {
      if (dp[n][k - i] && sum1 % k + i >= k) {
        flag = true;
        break;
      }
    }
    if (flag)
      cout << ans + 1 << endl;
    else
      cout << ans << endl;
  }
  return 0;
}
