Problem Description

TMJN loves anime very much.
Last night, he planned to watch $ N $ anime series. Each anime is numbered from $ 1 $ to $ N $, and the start time of the $ i $-th anime is $ A_i $ and the end time is $ B_i $.
However, he was tired last night and woke up in the morning without realizing it!

Yes, he fell asleep without watching any anime.
But fear not, this TMJN can time-travel!
So, he decided to time-travel and watch all the anime. However, time-traveling is physically exhausting, so he wants to minimize the time he travels back.

Now, the current time when TMJN woke up is $ T $.
TMJN can instantly change the TV channel, but he cannot watch multiple anime simultaneously.
Also, once he starts watching an anime, he will watch it till the end. He will never switch channels in the middle of watching an anime to watch another one.

At that time, output the minimum total time TMJN needs to travel back and the order in which he should watch the anime to achieve this.

Input Format

The input is given from the standard input in the following format:

$ N $ $ T $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ... $ A_{N-1} $ $ B_{N-1} $ $ A_N $ $ B_N $

Output Format

Output $ N+1 $ lines.
The first line should contain the minimum total time TMJN needs to travel back.
The $ i+1 $ $(1 \leq i \leq N)$ line should contain the number of the anime to be watched $ i $-th.
If there are multiple answers with the minimum total time, you can output any of them.

Sample Input and Output

Sample Input #1

3 141
5 9
26 53
58 97

Sample Output #1

136
1
2
3

Sample Input #2

5 10
0 10
2 5
6 9
1 8
5 7

Sample Output #2

25
2
5
3
4
1

Sample Input #3

7 30
1 15
23 25
13 21
0 5
18 20
4 11
19 22

Sample Output #3

47
6
4
1
3
5
7
2

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 10^5$
• $1 \leq T \leq 10^9$
• $0 \leq A_i$

Subtasks

This task has $ 3 $ subtasks:

1. (250 points) There is no pair $ (i, j) $ $(i \neq j)$ where $A_i \leq A_j$. In other words, no two anime are broadcast simultaneously.
2. (250 points) $ A_1 = 0, B_1 = T $ is satisfied.
3. (500 points) No additional constraints.

Sample Explanation 1

Watching anime $ 1 $, anime $ 2 $, and anime $ 3 $ in that order results in a total time-travel of $ 136 $. There is no other order that results in a shorter total time-travel. Note that this input example satisfies the constraints of subtask $ 1 $.

Sample Explanation 2

For example, watching anime $ 2 $, anime $ 5 $, anime $ 3 $, anime $ 4 $, and anime $ 1 $ in that order results in a total time-travel of $ 25 $. There is no other order that results in a shorter total time-travel. Note that this input example satisfies the conditions of subtask $ 2 $.

见题面 Input 部分

见题面 Output 部分