using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
    public static List<KittenNode> nodes = new List<KittenNode>();
    public static List<KittenNode> nodesStartTime = new List<KittenNode>();
    public static List<KittenNode> result = new List<KittenNode>();
    public static void Main()
    {
        nodes = new List<KittenNode>();

        //Accept input for kittens and beds.
        string[] startingConditions = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.None);
        int kittens = int.Parse(startingConditions[0]), beds = int.Parse(startingConditions[1]);

        //Initialize node list
        for (int i = 0; i < kittens; i++)
        {
            string[] demand = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.None);
            KittenNode newNode = new KittenNode(int.Parse(demand[0]), int.Parse(demand[1]), null);
            nodes.Add(newNode);
        }
        //Sort nodes by ascending exit times
        nodes = nodes.OrderBy(o => o.exitTime).ToList();
        //Sort nodesStartTime by ascending start times
        nodesStartTime = nodes.OrderBy(o => o.arrivalTime).ToList();

        CacheIntersectionResults();

        int catCount = 0;
        //Count the cats that fit into each bed and add them together.
        for (int i = 0; i < beds; i++)
        {
            KittenNode startingNode = FindOptimalNode(nodes, nodesStartTime, beds - i);
            catCount += CountCats(startingNode, beds - i);
        }
        //Output amount of cats.
        Console.WriteLine(catCount);
        Console.ReadLine();
    }


    public static int CountCats(KittenNode startingNode, int consideredNodeCount)
    {
       //If no cats are left in nodes, return.
        if (startingNode.exitTime == int.MaxValue)
            return 0; //No more cats

        //If more cats exist in nodes, find optimal node path for this bed.
        FindOptimalNodePath(startingNode, new List<KittenNode>(nodes), new List<KittenNode>(nodesStartTime), consideredNodeCount);

        //Count the cats and remove them from 'nodes'.
        int catCount = result.Count;
        foreach (KittenNode resultNode in result)
        {
            nodes.Remove(resultNode);
            nodesStartTime.Remove(resultNode);
            //foreach (KittenNode node in nodes) // K * N^2
            //{
            //    if (node.intersections != null && node.intersections.Contains(resultNode))
            //        node.intersections.Remove(resultNode);
            //}
        }
        result.Clear();
        return catCount;
    }
    public static void FindOptimalNodePath(KittenNode current, List<KittenNode> tempNodes, List<KittenNode> tempNodesStartTime, int consideredNodeCount)
    {
        //Remove current node from consideration.
        tempNodes.Remove(current);
        tempNodesStartTime.Remove(current);
        //Add current node to result.
        result.Add(current);

        // Find and remove all unreachable nodes
        List<KittenNode> removeList = new List<KittenNode>();
        for (int i = 0; i < tempNodes.Count; i++)
            if (tempNodes[i].arrivalTime < current.exitTime)
                removeList.Add(tempNodes[i]);
        foreach (KittenNode node in removeList)
        {
            tempNodes.Remove(node);
            tempNodesStartTime.Remove(node);
        }

        //If no more potential nodes exist, go to next loop or exit.
        if (tempNodes.Count == 0)
            return;
        //If more potential nodes exist, keep searching for optimal path.
        else
        {
            current = FindOptimalNode(tempNodes, tempNodesStartTime, consideredNodeCount); //K^2
            FindOptimalNodePath(current, tempNodes, tempNodesStartTime, consideredNodeCount); //K*N*Log(N)
        }
    }

    public static void CacheIntersectionResults()
    {
        //For all considered nodes, count the amount of intersections for each.
        //Intersection is defined by the starting point of a given node falling between the starting point and end point of a considered node.
        for (int i = 0; i < nodes.Count; i++)
        {
            nodes[i].intersections = new List<KittenNode>();
            for (int j = 0; j < nodesStartTime.Count; j++)
            {
                if (nodes[i].arrivalTime < nodesStartTime[j].arrivalTime && nodes[i].exitTime > nodesStartTime[j].arrivalTime)
                    nodes[i].intersections.Add(nodesStartTime[j]);
                else if (nodes[i].exitTime < nodesStartTime[j].arrivalTime)
                    break;
            }
        }
    }

    public static KittenNode FindOptimalNode(List<KittenNode> nodes, List<KittenNode> nodesStartTime, int consideredNodeCount)
    {
        //If no more nodes exist, return invalid node.
        if (nodes.Count == 0)
            return new KittenNode(0, int.MaxValue, null);
        //If amount of beds exceed amount of kittens or only one bed is available, return the lowest exit time.
        else if (nodes.Count < consideredNodeCount || consideredNodeCount == 1)
            return nodes[0];

        KittenNode currentNode = new KittenNode(0, int.MaxValue, null);
        int highestIntersectionCount = -1;
        //Iterate through intersections to find the highest amount.
        for (int i = 0; i < consideredNodeCount; i++)
            if (nodes[i].intersections.Count > highestIntersectionCount)
            {
                highestIntersectionCount = nodes[i].intersections.Count;
                //If two nodes have the same amount of intersections, select the one with lowest exit time. (Happens automatically due to sorting of 'nodes' list)
                currentNode = nodes[i];
            }

        return currentNode;
    }

    public class KittenNode
    {
        public KittenNode(int arrivalTime, int exitTime, List<KittenNode> intersections)
        {
            this.arrivalTime = arrivalTime;
            this.exitTime = exitTime;
            this.intersections = intersections;
        }
        public List<KittenNode> intersections;
        public int arrivalTime, exitTime;
    }
}