Description

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

Format

Input

输入共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间。（中间用空格隔开。）格式为
$n$
$b_1 e_1$
……
$b_n e_n$

Output

输出共两行，第一行为满足要求的活动所占用的总时间t。(可以理解为选择的活动中最后一个活动的结束时间) 第二行为最大集合中的活动序号。每个数据见用一个空格隔开。

Samples

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

Limitation

1s, 1024KiB for each test case.