说明

缤纷的游行活动，聚集了大量的人潮，大家穿着鲜艳的服装，排队一个一个往前移动。整个队伍共有 $n$ 个人，其中从头数来第 $i$ 个人的服装上有出现编号为 $l_i, l_i + 1, \dots, r_i$ 的颜色。

为了让活动更有特色，游行的总指挥决定把参加游行队伍分成若干个小队，其中每个小队为原本队伍的连续片段，而每个人都属于恰一个小队。每个小队的得分为队中成员服装的多样性，也就是有出现在至少一个队员服装上的颜色编号的种类数。整个队伍的总分即为各个小队的得分加总。

总指挥尚未确定该将整个队伍分成几个小队，他想知道对于所有 $x = 1, 2, \dots,k$，若将队伍分成恰 $x$ 个小队，队伍的总分最大可以是多少？请写一支程序帮助总指挥。

输入格式

$$\begin{aligned} &n \; k \\ &l_1 \; r_1 \\ &l_2 \; r_2 \\ &\vdots \\ &l_n \; r_n \end{aligned}$$

• $n$ 为整个队伍的人数。
• $k$ 为总指挥希望的小队数量上限。
• $l_i, r_i$ 代表第 $i$ 个人服装上出现的颜色编号为 $l_i, l_i + 1, \dots, r_i$。

输出格式

$$\begin{aligned} &ans_1 \; ans_2 \; \cdots \; ans_k \end{aligned}$$

• $ans_x$ 代表分成恰 $x$ 个小队的总分最大值。

5 1
3 3
5 7
2 6
10 11
11 12

9

5 5
1 3
2 5
3 6
3 7
5 6

7 11 14 16 18

10 10
1 1
1 1
1 1
3 3
3 3
2 2
3 3
1 1
2 2
1 1

3 6 7 8 9 10 10 10 10 10

提示

数据限制

• $1 \le n\le 10^5$。
• $1 \le k\le \min(n, 20)$。
• $1 \le l_i \le r_i \le 10^9$。
• 输入的数皆为整数。

评分说明

本题共有四组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分數	额外输入限制
1	6	$k = 1$。
2	15	$n \le 500$。
3	41	$1 \le l_i = r_i \le 10^5$。
4	38	无额外限制。