package main

import (
	"bufio"
	"fmt"
	"os"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(reader, &n, &k)

	a := make([]int64, n)
	b := make([]int64, n)
	var Sa, Sb int64

	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &a[i], &b[i])
		Sa += a[i]
		Sb += b[i]
	}

	if Sa%int64(k)+Sb%int64(k) < int64(k) {
		fmt.Println((Sa + Sb) / int64(k))
		return
	}

	dp := make([]bool, k)
	dp[0] = true
	newDp := make([]bool, k)

	for i := 0; i < n; i++ {
		if a[i]+b[i] >= int64(k) {
			L := max(0, int(int64(k)-b[i]))
			R := min(int(a[i]), k)

			copy(newDp, dp)

			for j := 0; j < k; j++ {
				if dp[j] {
					start := j + L
					end := j + R
					if end < k {
						for v := start; v <= end; v++ {
							newDp[v] = true
						}
					} else if start >= k {
						for v := start; v <= end; v++ {
							newDp[v-k] = true
						}
					} else {
						for v := start; v < k; v++ {
							newDp[v] = true
						}
						for v := k; v <= end; v++ {
							newDp[v-k] = true
						}
					}
				}
			}
			copy(dp, newDp)
		}
	}

	targetL := int(int64(k) - (Sb % int64(k)))
	targetR := int(Sa % int64(k))

	found := false
	for v := targetL; v <= targetR; v++ {
		if dp[v] {
			found = true
			break
		}
	}

	if found {
		fmt.Println((Sa + Sb) / int64(k))
	} else {
		fmt.Println((Sa + Sb)/int64(k) - 1)
	}
}