#include <bits/stdc++.h>
using namespace std;
const int N = 510;
bool dp[N][N];
int n, k;
int a[N], b[N];
int main() {
  cin >> n >> k;
  long long sum1 = 0, sum2 = 0;
  long long ans = 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;
  if (sum1 % k + sum2 % k < k) {
    printf("%lld\n", ans);
    return 0;
  } else {
    bool flag = false;
    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;
          }
        }
    for (int i = 0; i <= sum1 % k; i++)
      if (dp[n][i] && sum2 % k + i >= k) {
        flag = true;
        break;
      }
    if (flag)
      printf("%lld\n", ans + 1);
    else
      printf("%lld\n", ans);
  }
  return 0;
}
