题目描述

繽紛的遊行活動，聚集了大量的人潮，大家穿著鮮艷的服裝，排隊一個一個往前移動。整個隊伍共有 $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	無額外限制。