题目描述

假设有一个需要使用某一资源的$\red{n}$个活动组成的集合$\red{S}$，$\red{S=\{1……n\}}$。该资源一次只能被一个活动占用，每一个活动有一个开始时间$\red{b_{i}}$和结束时间$\red{e_{i}(b_{i}<=e_{i})}$。若$\red{b_{i}>=e_{j}}$或者$\red{b_{j}>=e_{i}}$，则活动$\red{i}$和活动$\red{j}$兼容。你的任务是：选择由互相兼容的活动组成的最大集合。

输入格式

共$\red{n+1}$行，其中第一行为$\red{n}$，第$\red{2}$行到第$\red{n+}$行表示$\red{n}$个活动的开始和结束时间，格式为

$\red{N（n<=1000）}$

$\red{b_{1} e_{1}}$

$\red{……}$

$\red{b_{n}e_{n}}$

输出格式

共两行，第一行为满足要求的活动所占用的时间$\red{t}$，第$\red{2}$行为最大集合中的活动序号，每个数之间用一个空格隔开。

样例

输入样例

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

输出样例

14
2 3 6 8