比较神仙的一道题。
第一问还比较简单一点：
t是否可行是单调的，考虑二分。
考虑对于两个人i，j合法的条件，设x(i)<x(j),那么$x(i)+\frac {a(i)*t^2}{2} < x(j)+\frac {a(j)*t^2}{2}$。
那么把x离散作为数组下标，t时间后的位置作为值，合法的最多人数为最长上升子序列。
将t时间后的位置再次离散，树状数组维护即可。
注意此序列的下标为离散后的x，并不是输入的‘老司机’的id，在求解第二问的时候要特别注意。
只需要判断最长上升子序列的长度与k的关系即可。
第二问就比较恶心了:
考虑求解最长上升子序列的同时记录前驱，那么可以找到一种合法的方案。
之后考虑字典序最小这条限制。
问题在于对于点i，之前可能有多个点是最大值，但是需要选择排序之后字典序最小的一个转移。
考虑dp的转移;一个点只能有他之前的一个点转移过来，所以是一个树形结构。
设f[j]=f[k]且都可以转移到i，那么考虑转移的树形结构，j，k处于同意深度，且lca及以上的序列相同。
当j->lca这条路径上的最小值小于k->lca这条路径的最小值时j比k更优。
那么只要倍增维护前驱及最小值即可。
用树状数组维护，转移和第一问类似。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define int LL
#define LL long long
using namespace std;
struct edge
{
int u,v,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].nxt
}ed[1000010];
int firs[100010],num_e;
#define f(x) firs[x]
struct node
{
LL x;int a,id,y;
#define x(i) A[i].x
#define y(i) A[i].y
#define a(i) A[i].a
#define id(i) A[i].id
double dis(int t){return x+a*t*t/2.0;}
}A[100010];
int n,k,ans,tx[100010];
bool v[100010];
vector<int>al1,al2;
struct TREE
{
LL C[100010];
#define lowbit(x) ((x)&(-(x)))
void clear(){memset(C,0,sizeof(C));}
void add(int x,int y){if(!x)return;while(x<=n)C[x]=max(C[x],y),x+=lowbit(x);}
LL ask(int x){if(!x)return 0;LL ans=0;while(x)ans=max(ans,C[x]),x-=lowbit(x);return ans;}
}T;
double a[200010],b[200010];LL c[200010],id[200010];int f[100010],pre[100010][26],prm[100010][26];
bool xy(int x,int y)
{
if(!x)return 0;
if(!y)return 1;
int t1=x,t2=y;
int minx=0x7fffffff,miny=0x7fffffff;
for(int i=25;i>=0;i--)
if(pre[x][i]!=pre[y][i])
minx=min(minx,prm[x][i]),
miny=min(miny,prm[y][i]),
x=pre[x][i],y=pre[y][i];
minx=min(minx,prm[x][0]);
miny=min(miny,prm[y][0]);
return minx<miny;
}
#define pair pair<int,int>
#define fir first
#define sec second
#define MP(a,b) make_pair(a,b)
struct TREE2
{
pair C[100010];
#define lowbit(x) ((x)&(-(x)))
void clear(){memset(C,0,sizeof(C));}
void add(int x,int y,int z)
{
if(!x)return;
while(x<=n)
{
if(y>C[x].fir)C[x]=MP(y,z);
else if(y==C[x].fir&&xy(z,C[x].sec))C[x].sec=z;
x+=lowbit(x);
}
}
pair ask(int x)
{
if(!x)return MP(0,0);pair ans=MP(0,0);
while(x)
{
if(C[x].fir>ans.fir)ans=C[x];
else if(C[x].fir==ans.fir&&xy(C[x].sec,ans.sec))ans.sec=C[x].sec;
x-=lowbit(x);
}
return ans;
}
}T2;
int solve(int t)
{
memset(f,0,sizeof(f));T.clear();
for(int i=1;i<=n;i++)a[y(i)]=A[i].dis(t),b[y(i)]=a[y(i)];
sort(b+1,b+n+1);int m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+m+1,a[i])-b;
int maxn=0;
for(int i=1;i<=n;i++)f[i]=T.ask(c[i]-1)+1,T.add(c[i],f[i]),maxn=max(maxn,f[i]);
if(maxn<k)return 0;if(maxn==k)return 1;return 2;
}
int sta[200010],top,dis[200010],du[200010];
inline int read();
inline void add(int u,int v);
signed main()
{
// freopen("driver2.in","r",stdin);
// freopen("in.txt","r",stdin);
// freopen("1.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++)
x(i)=read(),a(i)=read(),id(i)=i,tx[i]=x(i);
sort(tx+1,tx+n+1);int m=unique(tx+1,tx+n+1)-tx-1;
for(int i=1;i<=n;i++)y(i)=lower_bound(tx+1,tx+m+1,x(i))-tx;
int l=0,r=86400,mid,ans=0;
while(l<r)
{
mid=(l+r+1)>>1;
int te=solve(mid);
if(te)ans=te,l=mid;
else r=mid-1;
}
printf("%lld\n",l);
if(ans==2){puts("-1");return 0;}
memset(f,0,sizeof(f));T2.clear();
for(int i=1;i<=n;i++)a[y(i)]=A[i].dis(l),b[y(i)]=a[y(i)],id[y(i)]=i;
sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+m+1,a[i])-b;
for(int i=1;i<=n;i++)
{
pair tem=T2.ask(c[i]-1);
f[i]=tem.fir+1;pre[id[i]][0]=tem.sec;prm[id[i]][0]=id[i];
for(int j=1;j<=25;j++)
pre[id[i]][j]=pre[pre[id[i]][j-1]][j-1],
prm[id[i]][j]=min(prm[id[i]][j-1],prm[pre[id[i]][j-1]][j-1]);
T2.add(c[i],f[i],id[i]);
}
for(int i=1;i<=n;i++)
if(f[i]>=k)
{
al2.clear();int now=id[i];
while(now){al2.push_back(now);now=pre[now][0];}
if(!al1.size()){al1=al2;continue;}
sort(al1.begin(),al1.end());
sort(al2.begin(),al2.end());
for(int j=0;j<k;j++)
if(al2[j]<al1[j]){al1=al2;break;}
else if(al2[j]>al1[j])break;
}
sort(al1.begin(),al1.end());
for(int i=0;i<k;i++)printf("%lld\n",al1[i]);
}
inline int read()
{
int s=0,f=1;char a=getchar();
while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}
while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
return s*f;
}