卧槽这题有点牛逼。
像我这种蒟蒻只看题面肯定没有什么头绪，所以只好看一眼数据范围，似乎只能依赖方案在 O(m\log) 内解决。
至于为什么会想到 dp ，应该只能靠感觉吧，这题一看就很有线性dp的味道。
所以由前面的想法可以大概先设个 f_i ，至于 i 的含义只能结合方案的性质和所求的东西来考虑。
先整理一下：一个方案由四个参数 T_i,L_i,R_i,C_i确定，而我们需要最小化 [1,n] 全部被覆盖的代价和。
那么 i 的含义只和 T_i,L_i,R_i 有关，而我们的最终状态中没有时间的限制，而 L_i,R_i 在地位上是对等的，所以我们不妨只从 R_i 考虑对 i 含义的设计。
接下来这一步应该只能靠经验了，因为最终状态是全部覆盖，所以可以看成是由前缀全部覆盖递推而来，落到状态设计上就是设 f_i 为覆盖前缀 [1,R_i] 的最小代价。
这样就可以自然的写出方程：
f_i=\min_{R_j-L_i+1\geq|T_j-T_i|}f_j+C_i
残念ながら...这是一个有后效性的方程，似乎并不能按照某种拓扑序转移，这时就要用上另一个套路。
给方程换一种写法：
f_i\leq f_j+C_i ,R_j-L_i+1\geq|T_j-T_i|
观察到方程很像一个三角不等式，启发我们往最短路去想，这时麻烦的只有边数是 O(m^2) 的，这时只能挖掘这张图的性质。
注意到 (这一步真的很自然) i 的所有入边权都是 C_i ，所以在 \texttt{Dijkstra} 中每个点只应被更新一次就可以得到最短路，剩下的都是无用更新，至多只有 O(m) 次松弛。
所以我们要做的事情就是每次取出优先队列的一个点，只松弛未被松弛过且满足条件的点，那么接下来就好做了，对于上面那个条件式子很容易用线段树维护。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long;
const int N=1e5+10;
int rd(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}return x;
}
int n,m;
struct D{
int t,l,r,c;
int f0(){return -t+l-1;}
int f1(){return t+l-1;}
}a[N];
ll f[N];
#define pii pair<ll,int>
priority_queue<pii,vector<pii>,greater<pii> >q;
struct st{
struct node{
int l,r,m;
int v[2];
}d[N<<2|1];
void pushup(int p){
int l=p<<1,r=l|1;
d[p].v[0]=min(d[l].v[0],d[r].v[0]);
d[p].v[1]=min(d[l].v[1],d[r].v[1]);
}
void build(int p,int l,int r){
d[p]={l,r,l+r>>1,0};
if(l==r){
if(a[l].l==1){
f[l]=a[l].c,q.push({f[l],l});
d[p].v[0]=d[p].v[1]=2e9;
return;
}
d[p].v[0]=a[l].f0();
d[p].v[1]=a[l].f1();
return;
}
build(p<<1,l,d[p].m);
build(p<<1|1,d[p].m+1,r);
pushup(p);
}
void modify(int p,int l,int r,int lim,int x,int op){
if(l>r||lim<d[p].v[op])return;
if(d[p].l==d[p].r){
f[d[p].l]=f[x]+a[d[p].l].c;
q.push({f[d[p].l],d[p].l});
d[p].v[0]=d[p].v[1]=2e9;
return ;
}
if(l<=d[p].m)modify(p<<1,l,r,lim,x,op);
if(r>d[p].m)modify(p<<1|1,l,r,lim,x,op);
pushup(p);
}
}t;
int main(){
m=rd(),n=rd();
for(int i=1;i<=n;++i){
a[i]={rd(),rd(),rd(),rd()};
f[i]=1e18;
}
sort(a+1,a+1+n,[](D x,D y)->bool{return x.t<y.t;});
t.build(1,1,n);
while(!q.empty()){
int x=q.top().second;q.pop();
t.modify(1,1,x-1,a[x].r-a[x].t,x,0);
t.modify(1,x+1,n,a[x].r+a[x].t,x,1);
}
ll ans=1e18;
for(int i=1;i<=n;++i){
if(a[i].r==m)
ans=min(ans,f[i]);
}
printf("%lld\n",(ans==1e18)?-1:ans);
return 0;
}