#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int INF = 0x3f3f3f3f;
const int maxn = 510;
pair<int, int> tmp[maxn];
int a[maxn], b[maxn];
long long dp[maxn][maxn];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d%d", a + i, b + i);
  long long suma = accumulate(a + 1, a + n + 1, 0ll),
            sumb = accumulate(b + 1, b + n + 1, 0ll);
  long long ans = suma / k + sumb / k;
  fill(dp[0] + 1, dp[0] + k, -inf);
  for (int i = 1; i <= n; ++i) {
    fill(dp[i] + 1, dp[i] + k, -inf);
    int rm = a[i] % k;
    for (int q = 0; q < k - rm; ++q) {
      dp[i][q + rm] = max(dp[i][q + rm], dp[i - 1][q] + a[i] - rm + b[i]);
    }
    for (int q = k - rm; q < k; ++q) {
      dp[i][q + rm - k] =
          max(dp[i][q + rm - k], dp[i - 1][q] + k + a[i] - rm + b[i]);
    }
    for (int low = max(0, k - b[i]), up = min(a[i], k), j = low; j <= up; ++j) {
      rm = (a[i] - j) % k;
      for (int q = 0; q < k - rm; ++q) {
        dp[i][q + rm] = max(dp[i][q + rm],
                            dp[i - 1][q] + k + a[i] - j - rm + b[i] - (k - j));
      }
      for (int q = k - rm; q < k; ++q) {
        dp[i][q + rm - k] =
            max(dp[i][q + rm - k],
                dp[i - 1][q] + (k << 1) + a[i] - j - rm + b[i] - (k - j));
      }
    }
  }
  for (int i = 0; i < k; ++i) ans = max(ans, dp[n][i] / k);
  printf("%lld\n", ans);
  return 0;
}
