30857번 - Lucky Draws 다국어

문제

The ICPC committee is planning a surprise event to cheer on the participating teams. The committee provides each team with a pair of two numbers, $A$ and $B$ ($A ≤ B$), before the competition, which will be used for the lucky draws after the competition. The committee wants to hold $K$ draws. In each draw, a single number $C$ is chosen by the committee, and all teams with a pair $(A, B)$ such that $A ≤ C ≤ B$ win in this draw. To make more teams happy, the committee wants to choose the $K$ numbers used in the $K$ draws in advance so that the most teams win. A team can win multiple times but is considered to have won once.

For example, five teams are participating in ICPC and their pairs are $(1, 2),ドル $(1, 4),ドル $(3, 6),ドル $(4, 7),ドル $(5, 6),ドル and $K = 2$. When the committee chooses two numbers 2ドル$ and 4ドル,ドル four teams with $(1, 2),ドル $(1, 4),ドル $(3, 6)$ and $(4, 7)$ win. The team with $(1, 4)$ wins twice because the pair contains both chosen numbers. In fact, all five teams can win if 2ドル$ and 5ドル$ are chosen. The maximum number of winning teams is five.

Given $n$ pairs of two integers for teams and the number of lucky draws $K,ドル write a program to output the maximum number of winning teams.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $K$ (1ドル ≤ n ≤ 10,000円,ドル 1ドル ≤ K ≤ n,ドル 1ドル ≤ n \times K ≤ 500,000円$), where $n$ is the number of teams and $K$ is the number of lucky draws. Each of the following $n$ lines contains two integers $A$ and $B$ that represent the pair of a team, where $-10^6 ≤ A ≤ B ≤ 10^6$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the maximum number of winning teams. Teams that win more than once should only be counted once.

제한

힌트