30109번 - 보물 상자

문제

여러분은 보물 지도를 열심히 분석해서 마침내 보물이 숨겨진 동굴에 도달하는 데 성공했다.

지금 여러분의 눈앞에는 보물이 담겨 있는 $N$개의 상자가 있다. 이 중 $i$번째 상자에는 $L_i, L_i + 1, \dots, R_i - 1, R_i$번 보물이 담겨 있다. 여러분은 수많은 보물 상자 중, 몇 개의 상자만을 골라 그 안에 있는 보물들을 모두 가져가고자 한다.

1ドル$ 이상 $K$ 이하의 모든 정수 $i$에 대해, 보물 상자를 $i$개 골랐을 때 들고 갈 수 있는 서로 다른 번호를 가진 보물 개수의 최댓값을 구해보자.

입력

첫째 줄에 두 정수 $N$과 $K$가 공백을 두고 주어진다. $(1 \le N \le 100\ 000$; 1ドル \le K \le \min(N, 300))$

다음 $N$개의 줄에 두 정수 $L_i, R_i$가 공백을 두고 주어진다. $(1 \le L_i \le R_i \le 10^{9})$

출력

$K$개의 줄에 걸쳐 한 줄에 하나씩 답을 출력한다. $i$번째 줄에는 $i$개의 보물 상자를 골랐을 때 들고 갈 수 있는 서로 다른 번호를 가진 보물 개수의 최댓값을 출력한다.

제한

힌트