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: interview

Starter code:

Solutions:
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 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)

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
        #print(bin(pre))
    ans=0
    for r in range(k):
        if pre >> r & 1: ans = max(ans, (sa - r) // k + (sb + r) // k)
    print(ans)

main()

#!/usr/bin/env python3
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')

#solve
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


#main
def __starting_point():
    solve()

__starting_point()