基准时间限制：1 秒 空间限制：262144 KB 分值: 20

Pinball的游戏界面由m+2行、n列组成。第一行在顶端。一个球会从第一行的某一列出发，开始垂直下落，界面上有一些漏斗，一共有m个漏斗分别放在第2~m+1行，第i个漏斗的作用是把经过第i+1行且列数在Ai~Bi之间的球，将其移到下一行的第Ci列。 使用第i个漏斗需要支付Di的价钱，你需要保留一些漏斗使得球无论从第一行的哪一列开始放，都只可能到达第m+2行的唯一 一列，求花费的最少代价。

 

(样例的图)

(我们保留2，4，5即可，代价为5+3+12=20)

 

Input

第一行两个数，m和n。m<=100000,2<=n<=1000000000

接下来m行，第i+1行描述第i个漏斗的属性，Ai,Bi,Ci,Di (1<=Ai<=Ci<=Bi<=n, 1<=Di<=1000000000)。

Output

若不存在一种方案能满足条件则输出-1，否则输出最小花费

Input示例

5 6

3 5 4 8

1 4 3 5

4 6 5 7

5 6 5 3

3 5 4 12

Output示例

20

最后一定经过同一个漏斗
枚举最后经过哪个漏斗，然后求出第1列和第n列到达这个漏斗的最小花费就好了 
考虑DP L[i]和R[i] 
L[i]表示从1下落使用漏斗i到达C[i]的最小话费 L[i]=min{L[j] : A[i]<=C[j]<=B[i]}+D[i]}
这种带修改的RMQ问题用个线段树就好了
当然要离散化列啦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define lson x<<1,l,mid

#define rson x<<1|1,mid+1,r

#define lc x<<1

#define rc x<<1|1

typedef long long ll;

const int N=1e5+,M=3e5+;

const ll INF=1e18;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,a[N],b[N],c[N],d[N];

int mp[M];

void iniMP(){

    sort(mp+,mp++mp[]);

    int p=;mp[++p]=mp[];

    for(int i=;i<=mp[];i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];

    mp[]=p;

}

int Bin(int v){

    int l=,r=mp[];

    while(l<=r){

        int mid=(l+r)>>;

        if(mp[mid]==v) return mid;

        else if(v<mp[mid]) r=mid-;

        else l=mid+;

    }

    return ;

}

ll t[M<<];

void build(int x,int l,int r){

    if(l==r) t[x]=INF;

    else{

        int mid=(l+r)>>;

        build(lson);

        build(rson);

        t[x]=min(t[lc],t[rc]);

    }

}

void segCha(int x,int l,int r,int p,ll v){

    if(l==r) t[x]=min(t[x],v);//!!!

    else{

        int mid=(l+r)>>;

        if(p<=mid) segCha(lson,p,v);

        else segCha(rson,p,v);

        t[x]=min(t[lc],t[rc]);

    }

}

ll segMin(int x,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[x];

    else{

        ll re=INF;

        int mid=(l+r)>>;

        if(ql<=mid) re=min(re,segMin(lson,ql,qr));

        if(mid<qr) re=min(re,segMin(rson,ql,qr));

        return re;

    }

}

ll L[N],R[N];

void solve(){

    build(,,mp[]);

    segCha(,,mp[],,);

//    printf("check %d %d\n",segMin(1,1,mp[0],2,5),segMin(1,1,mp[0],1,5));

    for(int i=;i<=n;i++){

        L[i]=segMin(,,mp[],a[i],b[i])+d[i];

        segCha(,,mp[],c[i],L[i]);

        //printf("L %d %d\n",i,L[i]);

    }

    build(,,mp[]);

    segCha(,,mp[],mp[],);

    for(int i=;i<=n;i++){

        R[i]=segMin(,,mp[],a[i],b[i])+d[i];

        segCha(,,mp[],c[i],R[i]);

        //printf("R %d %d\n",i,R[i]);

    }

    ll ans=INF;

    for(int i=;i<=n;i++) ans=min(ans,L[i]+R[i]-d[i]);

    if(ans<INF) printf("%lld",ans);

    else puts("-1");

}

int main(){

//    freopen("in.txt","r",stdin);

    n=read();m=read();

    mp[++mp[]]=;mp[++mp[]]=m;

    for(int i=;i<=n;i++){

        mp[++mp[]]=a[i]=read();

        mp[++mp[]]=b[i]=read();

        mp[++mp[]]=c[i]=read();

        d[i]=read();

    }

    iniMP();

    //for(int i=1;i<=mp[0];i++) printf("mp %d %d\n",i,mp[i]);

    for(int i=;i<=n;i++) a[i]=Bin(a[i]),b[i]=Bin(b[i]),c[i]=Bin(c[i]);

    solve();

}