Gym 313459F

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e4+7;

struct Task{
    int s,e,a,ID;
};

inline bool operator <(const Task &a,const Task &b){
    return a.e<b.e;
}

int pre[N];
Task T[N];
db w[N];
db f[N];
db score[N];
int Rank[N];

inline bool cmp(const int &a,const int &b){
    return score[a]>score[b];
}

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int n,m;r(n),r(m);
    for(int i=1;i<=n;++i){
        r(T[i].s),r(T[i].e),r(T[i].a);
        T[i].ID=i;
    }
    sort(T+1,T+n+1);
    for(int i=1;i<=n;++i){
        int l=0,r=i-1,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(T[mid].e<=T[i].s)l=mid+1,pre[i]=mid;
            else r=mid-1;
        }
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            scanf("%lf",&w[j]);
        }
        for(int j=1;j<=n;++j){
            f[j]=max(f[j-1],f[pre[j]]+w[T[j].ID]*T[j].a);
        }
        score[i]=f[n];
        Rank[i]=i;
    }
    sort(Rank+1,Rank+m+1,cmp);
    for(int i=1;i<=3;++i){
        printf("%d %.2lf\n",Rank[i],score[Rank[i]]);
    }
    return 0;
}