Problem Description

A colorful parade attracts a huge crowd. Everyone wears bright clothes and moves forward in a line, one by one. There are $n$ people in the whole line. For the $i$-th person from the front, the colors that appear on their clothes have indices $l_i, l_i + 1, \dots, r_i$.

To make the event more distinctive, the parade commander decides to split the line into several small teams. Each team is a consecutive segment of the original line, and each person belongs to exactly one team. The score of a team is the diversity of the team members' clothes, i.e., the number of distinct color indices that appear on at least one member's clothes. The total score of the whole line is the sum of the scores of all teams.

The commander has not yet decided how many teams to split into. For all $x = 1, 2, \dots, k$, he wants to know: if the line is split into exactly $x$ teams, what is the maximum possible total score? Please write a program to help the commander.

Input Format

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

• $n$ is the number of people in the whole line.
• $k$ is the upper limit on the number of teams desired by the commander.
• $l_i, r_i$ mean that the color indices appearing on the $i$-th person's clothes are $l_i, l_i + 1, \dots, r_i$.

Output Format

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

• $ans_x$ is the maximum total score when splitting into exactly $x$ teams.

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

Hint

Constraints

• $1 \le n\le 10^5$.
• $1 \le k\le \min(n, 20)$.
• $1 \le l_i \le r_i \le 10^9$.
• All input values are integers.

Scoring

This problem has four subtasks, with the constraints as follows.
Each subtask may contain one or more testdata sets. You will receive the score for a subtask only if you pass all testdata in that subtask.

Subtask	Score	Additional Input Constraints
1	6	$k = 1$.
2	15	$n \le 500$.
3	41	$1 \le l_i = r_i \le 10^5$.
4	38	No additional constraints.

Translated by ChatGPT 5