在一个风和日丽的下午,Star从群玉阁跳了下来,落在了一座山的山顶上,发现他的正前方有很多山。
于是,他很好奇请钟离移走一些山后,他最多能看到多少座山。
Star前方有 n 座山,他知道每座山相对自己所在的这座的高度 h_i 和距离 d_i 。钟离可以移走任何一座山,也可以不移。
求他能看到的最多的山的个数 m ,和看到的是哪几个山 (输出一种方案)。
第 1 行一个整数 n ,表示山的个数。
接下来 n 行每行两个整数 h_i , d_i ,表示相对高度和距离,数据保证 d_i 递增。
第一行一个整数 m 表示最多能看到的山的个数。
第二行输出一种可行的方案,按照从近到远的顺序输出山的编号,每个数之间用空格隔开。若存在多组解,输出字典序最小的一组。
7 1 1 4 2 3 3 8 4 20 5 18 6 35 7
4 1 2 5 7
10 -23 2 33 3 11 4 -107 7 30 8 46 9 -94 12 239 13 39 14 -330 19
5 1 3 5 6 8
如图
可行的方案有 [1, 2, 5, 7] , [1, 4, 5, 7] , [3, 4, 5, 7] 三种,其中 [1, 2, 5, 7] 最小。
注意:如果山顶在同一条线上视为后面的那座看不到
对于 50\% 的数据,满足 0<n\le10000 .
对于另外 50\% 的数据,满足 10000<n\le200000 .
对于 100\% 的数据,满足 0<n\le200000 , 0<d_i<10^9 , -10^9 \le h_i \le 10^9 .