P6044 [POI 2018] Prawnicy

**This problem is translated from [POI XXV - Stage I](https://sio2.mimuw.edu.pl/c/oi25-1/dashboard/) “[Prawnicy](https://sio2.mimuw.edu.pl/c/oi25-1/p/pra/)”.**

The “Bajtazar & Son” law firm has just received an order from a very important client. The case is serious and urgent, and it requires holding a meeting with the firm’s lawyers. Each lawyer has a fixed free time interval during which they can attend the meeting. You should choose $k$ lawyers so that the meeting time (i.e., the time when all of them are free) is as long as possible. [Brief statement](https://www.luogu.com.cn/problem/U252799).

The first line contains two integers $n$ and $k\ (1\le k\le n)$, separated by a single space, representing the number of lawyers employed by the firm and the number of lawyers required for the meeting. The next $n$ lines: the $i$-th line contains two integers $a_i$ and $b_i\ (1\le a_i

Print an integer in the first line, the maximum possible duration of the meeting. You may assume that it is possible to hold a meeting with at least $1$ person. In the second line, print $k$ integers separated by spaces, representing the indices (starting from $1$) of the lawyers attending the meeting. If there are multiple correct answers, your program may output any one of them.

#### Sample Explanation The maximum possible duration of a meeting with three lawyers is $4$. Lawyers numbered $1$, $2$, and $4$ can attend, with the meeting lasting from $4$ to $8$. Another equally good solution is to choose lawyers $2$, $4$, and $5$, with the meeting lasting from $5$ to $9$.  #### Additional Samples See `pra/pra*.in` and `pra/pra*.out`: - Additional sample $1$: $1$ test case, $n=7$, $k=3$, and there are two ways to choose the lawyers. - Additional sample $2$: $1$ test case, $n=k=1000$, $a_i=i$, $b_i=10^6+i$. - Additional sample $3$: $1$ test case, $n=1000$, $k=1$, $a_i=2i-1$, $b_i=2i$. #### Constraints and Notes The test set is divided into the following subtasks. The tests for each subtask consist of one or more separate test cases. | Subtask # | Additional constraints | Score | |:---------:|:----------------------:|:-----:| | $1$ | $n\le 20$ | $20$ | | $2$ | $n\le 300$，$a_i,b_i\le 300$ | $15$ | | $3$ | $n\le 5000$ | $15$ | | $4$ | $n\le 10^6$，$k\in \{1,n\}$ | $15$ | | $5$ | $n\le 10^6$ | $35$ | If your program prints the correct duration in the first line but the rest of the output is incorrect, you will receive $40\%$ of the score. Translated by ChatGPT 5