Phoenix is picking berries in his backyard. There are $n$ shrubs, and each shrub has $a_i$ red berries and $b_i$ blue berries.

Each basket can contain $k$ berries. But, Phoenix has decided that each basket may only contain berries from the same shrub or berries of the same color (red or blue). In other words, all berries in a basket must be from the same shrub or/and have the same color.

For example, if there are two shrubs with $5$ red and $2$ blue berries in the first shrub and $2$ red and $1$ blue berries in the second shrub then Phoenix can fill $2$ baskets of capacity $4$ completely:   the first basket will contain $3$ red and $1$ blue berries from the first shrub;  the second basket will contain the $2$ remaining red berries from the first shrub and $2$ red berries from the second shrub. 

Help Phoenix determine the maximum number of baskets he can fill completely!


-----Input-----

The first line contains two integers $n$ and $k$ ($ 1\le n, k \le 500$) — the number of shrubs and the basket capacity, respectively.

The $i$-th of the next $n$ lines contain two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) — the number of red and blue berries in the $i$-th shrub, respectively.


-----Output-----

Output one integer — the maximum number of baskets that Phoenix can fill completely.


-----Examples-----
Input
2 4
5 2
2 1

Output
2

Input
1 5
2 3

Output
1

Input
2 5
2 1
1 3

Output
0

Input
1 2
1000000000 1

Output
500000000



-----Note-----

The first example is described above.

In the second example, Phoenix can fill one basket fully using all the berries from the first (and only) shrub.

In the third example, Phoenix cannot fill any basket completely because there are less than $5$ berries in each shrub, less than $5$ total red berries, and less than $5$ total blue berries.

In the fourth example, Phoenix can put all the red berries into baskets, leaving an extra blue berry behind.

Difficulty: VERY_HARD
Tags: Dynamic programming

Complete search

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	(n, k) = RL()
	arr = [RLL() for _ in range(n)]
	sa = sb = 0
	for (a, b) in arr:
		sa += a
		sb += b
	res = sa // k + sb // k
	(da, db) = (sa % k, sb % k)
	if res == (sa + sb) // k:
		print(res)
		exit()
	dp = [0] * k
	dp[0] = 1
	for i in range(n):
		(a, b) = arr[i]
		(l, r) = (max(0, k - a), min(k, b + 1))
		for (ind, v) in enumerate(dp[:]):
			if v:
				for j in range(l, r):
					dp[(ind + j) % k] = 1
	for i in range(k):
		if dp[i]:
			res = max(res, (sa + i) // k + (sb - i) // k)
	print(res)
main()


import itertools as it
(n, k) = map(int, input().split())
bushes = [tuple(map(int, input().split())) for i in range(n)]
red = sum((bush[0] for bush in bushes))
blue = sum((bush[1] for bush in bushes))
r0 = red % k
r1 = blue % k
max_ = (red + blue) // k
if r0 + r1 < k:
	print(max_)
	exit()
r0_required = set(range(r0 + r1 - k + 1))
r0_available = {r0}
for (red, blue) in bushes:
	if red + blue < k:
		continue
	max_red = min(k - 1, red)
	min_red = max(0, k - blue)
	for (ex_r, diff) in it.product(list(r0_available), range(min_red, max_red + 1)):
		new_r = ex_r - diff
		if new_r < 0:
			new_r += k
		if new_r in r0_required:
			print(max_)
			exit()
		r0_available.add(new_r)
print(max_ - 1)


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list([int(x) - 1 for x in input().split()])

def II():
	return int(input())

def IF():
	return float(input())

def S():
	return input().rstrip()

def LS():
	return S().split()

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def solve():
	(n, k) = LI()
	ab = LIR(n)
	dp = [False] * k
	dp[0] = True
	A = 0
	B = 0
	for (a, b) in ab:
		ndp = dp[::1]
		A += a
		B += b
		for i in range(k):
			if dp[i]:
				for j in range(max(k - a, 1), min(k, b + 1)):
					ndp[(i + j) % k] = True
		dp = ndp[::1]
	ans = A // k + B // k
	for i in range(k):
		if dp[i]:
			ans = max(ans, (A + i) // k + (B - i) // k)
	print(ans)
	return

def __starting_point():
	solve()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	(n, k) = MI()
	ab = LLI(n)
	pre = 1
	sa = sb = 0
	mask = (1 << k) - 1
	for (a, b) in ab:
		sa += a
		sb += b
		if a + b < k:
			continue
		mn = max(k - b, 0)
		mx = min(a, k - 1)
		now = pre
		for s in range(mn, mx + 1):
			now |= pre << s
		now |= now >> k
		now &= mask
		pre = now
	ans = 0
	for r in range(k):
		if pre >> r & 1:
			ans = max(ans, (sa - r) // k + (sb + r) // k)
	print(ans)
main()


(n, k) = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
base = sum(a) // k + sum(b) // k
A = sum(a) % k
B = sum(b) % k
data = [False for i in range(k)]
for i in range(n):
	ndata = [data[j] for j in range(k)]
	for j in range(1, k):
		if j <= a[i] and k - j <= b[i]:
			ndata[j] = True
			for x in range(1, k):
				prev = (x - j) % k
				if data[prev]:
					ndata[x] = True
	data = ndata
check = False
for i in range(1, k):
	if i <= A and k - i <= B:
		if data[i]:
			check = True
print(base + check)


from math import sqrt
from collections import defaultdict
from functools import lru_cache
it = lambda : list(map(int, input().strip().split()))
INF = float('inf')

def solve():
	(n, k) = it()
	tt = 0
	rt = 0
	bt = 0
	berries = []
	for _ in range(n):
		(red, blue) = it()
		berries.append([red, blue])
		tt += red
		tt += blue
		rt += red
		bt += blue
	re = rt % k
	be = bt % k
	if re + be <= tt % k:
		return tt // k

	@lru_cache(None)
	def dp(i, re, be):
		if re == 0 or be == 0:
			return True
		if i == n:
			return False
		if dp(i + 1, re, be):
			return True
		(red, blue) = berries[i]
		for j in range(min(red + 1, k + 1)):
			if k - j > blue:
				continue
			if dp(i + 1, (re - j + k) % k, (be + j) % k):
				return True
		return False
	return tt // k if dp(0, re, be) else tt // k - 1
print(solve())


(n, k) = map(int, input().split())
totA = 0
totB = 0
A = [0]
B = [0]
dp = []
for i in range(n + 1):
	h = []
	for j in range(k):
		h.append(False)
	dp.append(h)
dp[0][0] = True
for i in range(n):
	(a, b) = map(int, input().split())
	A.append(a)
	B.append(b)
	totA += a
	totB += b
for i in range(1, n + 1):
	for j in range(k):
		dp[i][j] = dp[i - 1][(j - A[i] % k + k) % k]
		for l in range(0, min(k - 1, A[i])):
			if (A[i] - l) % k + B[i] >= k:
				dp[i][j] |= dp[i - 1][(j - l) % k]
ans = 0
for i in range(k):
	if dp[n][i]:
		ans = max(ans, (totA + totB - i) // k)
print(ans)


def check(k, aas, bs, a_rem, b_rem):
	if a_rem + b_rem < k:
		return False
	a_lo = k - b_rem
	a_hi = a_rem
	rems = set()
	rems.add(0)
	for (a, b) in zip(aas, bs):
		if a + b < k:
			continue
		for i in range(max(0, k - b), min(a, k) + 1):
			rem = i % k
			for j in list(rems):
				rems.add((j + rem) % k)
	for rem in rems:
		if rem >= a_lo and rem <= a_hi:
			return True
	return False
(n, k) = [int(x) for x in input().split()]
aas = []
bs = []
a_total = 0
b_total = 0
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	aas.append(a)
	bs.append(b)
	a_total += a
	b_total += b
ans = a_total // k + b_total // k
if check(k, aas, bs, a_total % k, b_total % k):
	print(ans + 1)
else:
	print(ans)


import copy
shroud = []
aBerrySum = 0
bBerrySum = 0
(n, k) = map(int, input().split())
isAllRemainderCovered = False
remainderCovered = [False for _ in range(k)]
remainderCovered[0] = True
for _ in range(n):
	(a, b) = map(int, input().split())
	shroud.append([a, b])
	aBerrySum += a
	bBerrySum += b
	if a >= k and b >= k:
		isAllRemainderCovered = True
	elif not isAllRemainderCovered and a + b >= k:
		newRemainderCovered = copy.copy(remainderCovered)
		for i in range(min(a + 1, k + 1)):
			if k - i <= b:
				for j1 in range(k):
					if remainderCovered[j1 % k]:
						newRemainderCovered[(j1 + i) % k] = True
		remainderCovered = newRemainderCovered
if isAllRemainderCovered:
	print((aBerrySum + bBerrySum) // k)
else:
	aRemainder = aBerrySum % k
	bRemainder = bBerrySum % k
	if aRemainder + bRemainder < k:
		print((aBerrySum + bBerrySum) // k)
	else:
		isRemainderCovered = False
		for i in range(aRemainder + 1):
			if k - i <= bRemainder and remainderCovered[i]:
				isRemainderCovered = True
				break
		if isRemainderCovered:
			print((aBerrySum + bBerrySum) // k)
		else:
			print((aBerrySum + bBerrySum) // k - 1)


MOD = 10 ** 9 + 7

def main():
	for _ in inputt(1):
		(n, k) = inputi()
		T = [0] * k
		T[0] = 1
		(A, B) = (0, 0)
		for _ in range(n):
			(a, b) = inputi()
			(A, B) = (A + a, B + b)
			(mi, ma) = (max(k - a, 1), min(k, b + 1))
			for (t, c) in list(enumerate(T)):
				if c:
					for i in range(mi, ma):
						T[(t + i) % k] = 1
		s = A // k + B // k
		for t in range(k):
			if T[t]:
				s = max((A + t) // k + (B - t) // k, s)
		print(s)
from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(1000)
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	if args:
		sys.stdout.write(str(args[0]))
		split = kwargs.pop('split', ' ')
		for arg in args[1:]:
			sys.stdout.write(split)
			sys.stdout.write(str(arg))
	sys.stdout.write(kwargs.pop('end', '\n'))

def debug(*args, **kwargs):
	print('debug', *args, **kwargs)
	sys.stdout.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip()
inputt = lambda t=0: range(t) if t else range(int(input()))
inputs = lambda : input().split()
inputi = lambda k=int: map(k, inputs())
inputl = lambda t=0, k=lambda : list(inputi()): [k() for _ in range(t)] if t else list(k())

def len(a):
	if isinstance(a, range):
		return -((a.start - a.stop) // a.step)
	return builtins.len(a)

def bisect_left(a, x, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	if key == None:
		key = do_nothing
	while lo < hi:
		mid = (lo + hi) // 2
		if key(a[mid]) < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def bisect_right(a, x, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	if key == None:
		key = do_nothing
	while lo < hi:
		mid = (lo + hi) // 2
		if x < key(a[mid]):
			hi = mid
		else:
			lo = mid + 1
	return lo

def insort_left(a, x, key=None, lo=0, hi=None):
	lo = bisect_left(a, x, key, lo, hi)
	a.insert(lo, x)

def insort_right(a, x, key=None, lo=0, hi=None):
	lo = bisect_right(a, x, key, lo, hi)
	a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right

def index(a, x, default=None, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	if key == None:
		key = do_nothing
	i = bisect_left(a, x, key, lo, hi)
	if lo <= i < hi and key(a[i]) == x:
		return a[i]
	if default != None:
		return default
	raise ValueError

def find_lt(a, x, default=None, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	i = bisect_left(a, x, key, lo, hi)
	if lo < i <= hi:
		return a[i - 1]
	if default != None:
		return default
	raise ValueError

def find_le(a, x, default=None, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	i = bisect_right(a, x, key, lo, hi)
	if lo < i <= hi:
		return a[i - 1]
	if default != None:
		return default
	raise ValueError

def find_gt(a, x, default=None, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	i = bisect_right(a, x, key, lo, hi)
	if lo <= i < hi:
		return a[i]
	if default != None:
		return default
	raise ValueError

def find_ge(a, x, default=None, key=None, lo=0, hi=None):
	if lo < 0:
		lo = 0
	if hi == None:
		hi = len(a)
	i = bisect_left(a, x, key, lo, hi)
	if lo <= i < hi:
		return a[i]
	if default != None:
		return default
	raise ValueError

class Tree:

	def __init__(n):
		self._n = n
		self._conn = [[] for _ in range(n)]
		self._list = [0] * n

	def connect(a, b):
		pass

class Sieve:

	def __init__(self):
		self._n = 6
		self._list = [2, 3, 5, 7, 11, 13]

	def extend(self, n):
		if n <= self._list[-1]:
			return
		maxbase = int(n ** 0.5) + 1
		self.extend(maxbase)
		begin = self._list[-1] + 1
		newsieve = [i for i in range(begin, n + 1)]
		for p in self.primerange(2, maxbase):
			for i in range(-begin % p, len(newsieve), p):
				newsieve[i] = 0
		self._list.extend([x for x in newsieve if x])

	def extend_to_no(self, i):
		while len(self._list) < i:
			self.extend(int(self._list[-1] * 1.5))

	def primerange(self, a, b):
		a = max(2, a)
		if a >= b:
			return
		self.extend(b)
		i = self.search(a)[1]
		maxi = len(self._list) + 1
		while i < maxi:
			p = self._list[i - 1]
			if p < b:
				yield p
				i += 1
			else:
				return

	def search(self, n):
		if n < 2:
			raise ValueError
		if n > self._list[-1]:
			self.extend(n)
		b = bisect(self._list, n)
		if self._list[b - 1] == n:
			return (b, b)
		else:
			return (b, b + 1)

	def __contains__(self, n):
		if n < 2:
			raise ValueError
		if not n % 2:
			return n == 2
		(a, b) = self.search(n)
		return a == b

	def __getitem__(self, n):
		if isinstance(n, slice):
			self.extend_to_no(n.stop + 1)
			return self._list[n.start:n.stop:n.step]
		else:
			self.extend_to_no(n + 1)
			return self._list[n]
sieve = Sieve()

def isprime(n):
	if n <= sieve._list[-1]:
		return n in sieve
	for i in sieve:
		if not n % i:
			return False
		if n < i * i:
			return True
prime = sieve.__getitem__
primerange = lambda a, b=0: sieve.primerange(a, b) if b else sieve.primerange(2, a)

def factorint(n):
	factors = []
	for i in sieve:
		if n < i * i:
			break
		while not n % i:
			factors.append(i)
			n //= i
	if n != 1:
		factors.append(n)
	return factors
factordict = lambda n: Counter(factorint(n))
main()


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = [None]
b = [None]
for _ in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
dp = [[None] * 505 for _ in range(505)]
totA = sum(a[1:])
totB = sum(b[1:])
dp[0][0] = True
for i in range(1, n + 1):
	for j in range(k):
		dp[i][j] = dp[i - 1][(j - a[i] % k + k) % k]
		for l in range(min(k - 1, a[i]) + 1):
			if (a[i] - l) % k + b[i] >= k:
				dp[i][j] = dp[i][j] or dp[i - 1][(j - l + k) % k]
ans = 0
for i in range(k):
	if dp[n][i]:
		ans = max(ans, (totA + totB - i) // k)
print(ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from functools import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

def lcm(a, b):
	return a * b // gcd(a, b)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res
t = 1
for i in range(t):
	(n, k) = RL()
	ans = 0
	res = []
	for i in range(n):
		(a, b) = RL()
		res.append([a, b])
	pre = [0]
	for (a, b) in res:
		pre.append((pre[-1] + a + b) % k)
	dp = [[-1] * k for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(n):
		(a, b) = res[i]
		for j in range(min(a, k - 1) + 1):
			c = (a - j + k - 1) // k
			need = c * k - (a - j)
			if b < need:
				continue
			for x in range(k):
				if dp[i][x] != -1:
					y = (pre[i] - x) % k
					dp[i + 1][(x + j) % k] = max(dp[i + 1][(x + j) % k], dp[i][x] + c + (x + j) // k + (b - need + y) // k)
	ans = max(dp[-1])
	print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	(n, k) = map(int, input().split())
	trees = [tuple(map(int, input().split())) for _ in range(n)]
	(r_mod, b_mod) = (0, 0)
	dp = array('b', [1] + [0] * (k - 1))
	next_dp = array('b', [0]) * k
	(r_total, b_total) = (0, 0)
	for (ri, bi) in trees:
		r_total += ri
		b_total += bi
		for r in range(k):
			if not dp[r]:
				continue
			next_dp[(r + ri) % k] = 1
			for (sub_r, sub_b) in zip(range(1, k), range(k - 1, 0, -1)):
				if sub_r <= ri and sub_b <= bi:
					next_dp[(r + ri - sub_r) % k] = 1
		(r_mod, b_mod) = ((r_mod + ri) % k, (b_mod + bi) % k)
		(dp, next_dp) = (next_dp, dp)
		for i in range(k):
			next_dp[i] = 0
	for (r, req_b) in zip(range(r_mod - 1, -1, -1), range(k - 1, -1, -1)):
		if dp[r] and b_mod >= req_b:
			print(r_total // k + b_total // k + 1)
			break
	else:
		print(r_total // k + b_total // k)
main()


import sys
readline = sys.stdin.readline

def merge(A, B):
	res = A[:]
	for i in range(len(A)):
		if A[i]:
			for j in range(len(B)):
				if B[j]:
					res[(i + j) % K] = 1
	return res
(N, K) = map(int, readline().split())
R = 0
B = 0
flag = False
table = [0] * K
table[0] = 1
for _ in range(N):
	(r, b) = map(int, readline().split())
	R += r
	B += b
	if r >= K and b >= K:
		flag = True
	elif r + b >= K:
		(st, en) = (max(0, K - b), min(K, r))
		t2 = [0] * K
		for i in range(st, en + 1):
			t2[i % K] = 1
		table = merge(table, t2)
if flag:
	print((R + B) // K)
elif R // K + B // K == (R + B) // K:
	print((R + B) // K)
else:
	pr = R % K
	pb = B % K
	ans = R // K + B // K
	for i in range(K):
		if table[i]:
			if (pr - i) % K + (pb - K + i) % K < K:
				ans += 1
				break
	print(ans)


(n, k) = map(int, input().split())
sumr = 0
sumb = 0
sumtot = 0
possr = [0] * k
possr[0] = 1
for i in range(n):
	(a, b) = map(int, input().split())
	sumr += a
	sumb += b
	sumtot += a
	sumtot += b
	tot = a + b
	poss2 = [0] * k
	for j in range(k):
		rest = a - j
		rest %= k
		if (rest + b >= k or rest == 0) and j <= a:
			for l in range(k):
				if possr[l] == 1:
					poss2[(l + j) % k] = 1
	for j in range(k):
		possr[j] = poss2[j]
sol1 = sumtot // k
sol2 = sumr // k + sumb // k
if sol1 == sol2:
	print(sol1)
else:
	i = 0
	while possr[i] == 0:
		i += 1
	sumr %= k
	sumb %= k
	sumr -= i
	sumb += sumr
	if sumb >= k:
		print(sol1)
	else:
		print(sol2)