#include <bits/stdc++.h>
using namespace std;
const int LIM = 5e5 + 3;
int arr[LIM + 3];
long long inf = 1e18;
int cnt[30];
int a[LIM + 3], b[LIM + 3];
long long Ans = 0;
long long sum_a = 0, sum_b = 0;
int n, k;
void pri(int i) { cout << char(i + 'a'); }
long long mx = 0;
int dp[505][505];
int solve(int i, int rema, int remb, int init) {
  if (init - (rema + remb) == k) {
    return 1;
  }
  if (i == n) return 0;
  int &ret = dp[i][rema];
  if (ret != -1) return ret;
  ret = 0;
  ret = solve(i + 1, rema, remb, init);
  if (a[i] + b[i] < k) return ret;
  for (int j = max(0, k - b[i]); j <= min(a[i], k - 1); j++) {
    int tmpa = (rema - j + k) % k;
    int tmpb = (remb - (k - j) + k) % k;
    ret |= solve(i + 1, tmpa, tmpb, init);
  }
  return ret;
}
int main() {
  memset(dp, -1, sizeof dp);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &b[i]);
    sum_a += a[i];
    sum_b += b[i];
  }
  if (solve(0, sum_a % k, sum_b % k, sum_a % k + sum_b % k))
    cout << sum_a / k + sum_b / k + 1 << endl;
  else
    cout << sum_a / k + sum_b / k << endl;
}
