Background

This problem is translated from POI XXV - Stage I “Prawnicy”.

Problem Description

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.

Input Format

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<b_i\le 10^9)$, separated by a single space, indicating that the $i$-th lawyer is free between time $a_i$ and time $b_i$.

Output Format

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.

6 3
3 8
4 12
2 6
1 10
5 9
11 12

4
1 2 4

Hint

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.

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