#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
using namespace std;
namespace Yorihime_Nao{
	template<class T> T MAX(T x,T y){
		return x>y?x:y;
	}
	template<class T> T MIN(T x,T y){
		return x<y?x:y;
	}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
		return MAX(x>y?x:y,arg...);
	}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
		return MIN(x<y?x:y,arg...);
	}
	template<class T> T lowbit(T x){
		return x&-x;
	}
	template<class T> void SWAP(T &x,T &y){
		T qwq;
		qwq=x;
		x=y;
		y=qwq;
		return;
	}
}
using namespace Yorihime_Nao;
const ll MAXN=505;
ll n,k;
ll a,b,sum;
ll dp[2][MAXN]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<k;i++)dp[0][i]=-0x7f7f7f7f7f;
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++)dp[i&1][j]=-0x7f7f7f7f7f;
		cin>>a>>b;
		for(int p=0;p<k;p++){
			ll lst_b=(sum%k+k-p)%k;
			for(int q=0;q<MIN(k,a+1);q++){
				ll now_b=((a+b)%k+k-q)%k;
				if(now_b>b)continue;
				dp[i&1][(p+q)%k]=MAX(dp[i&1][(p+q)%k],dp[(i&1)^1][p]+(p+q)/k+(lst_b+now_b)/k+(a+b-now_b-q)/k);
			}
		}
		sum+=(a+b);
	}
	ll ans=0;
	for(int i=0;i<k;i++)ans=MAX(ans,dp[n&1][i]);
	cout<<ans; 
	return 0;
}