这是一道环上的问题，我们先将一个环展开，再复制一次。
这样，任何一个合法方案一定对应在转换后的序列的一些连续的区间，使得它们的并的长度大于等于圈长。
然后，我们将区间合并一下（就是将一些被其他区间包含的区间去掉）。
假设某个答案的区间是r1,r2,r3,...rk，我们可以让ri为"与ri-1连接的右端点最靠右的区间“，明显这样不会不原来的答案劣。
所以，一旦确定了起点，那么在该起点的情况下最优的覆盖圆环的方案就确定了，确定了区间，我们可以用倍增的思想来判断一串连续区间覆盖len最少需要多少个，（有点像跳跃式的LCA求法中用倍增的思想）。这个O(logn)可搞，然后枚举起点是O(n），总的复杂度是O(nlogn)。
/**************************************************************
Problem: 1780
User: idy002
Language: C++
Result: Accepted
Time:2124 ms
Memory:33796 kb
****************************************************************/ #include <cstdio>
#include <vector>
#include <algorithm>
#define fprintf(...)
#define maxn 200010
#define maxp 18
using namespace std; struct Rng {
int lf, rg;
Rng(){}
Rng( int lf, int rg ):lf(lf),rg(rg){}
bool operator<( const Rng &b ) const { return lf<b.lf || (lf==b.lf&&rg>b.rg); }
}; int len, n;
Rng rng[maxn]; int tot;
vector<int> stk;
bool mark[maxn];
int nxt[maxn][maxp+], dis[maxn][maxp+]; int main() {
scanf( "%d%d", &len, &n );
for( int i=,lf,ln; i<=n; i++ ) {
scanf( "%d%d", &lf, &ln );
rng[++tot] = Rng(lf,lf+ln);
}
for( int i=,otot=tot; i<=otot; i++ )
rng[++tot] = Rng( rng[i].lf+len, rng[i].rg+len );
sort( rng+, rng++tot );
for( int i=; i<=tot; i++ )
if( !mark[i] ) {
stk.push_back( i );
fprintf( stderr, "Got [%d,%d]\n", rng[i].lf, rng[i].rg );
for( int j=i+; j<=tot; j++ )
if( rng[j].rg<=rng[i].rg ) mark[j]=true;
else break;
}
for( int t=; t<stk.size(); t++ ) {
int u=stk[t];
nxt[u][] = u;
dis[u][] = ;
for( int tt=t+; tt<stk.size(); tt++ ) {
int v=stk[tt];
if( rng[v].lf<=rng[u].rg ) {
nxt[u][] = v;
dis[u][] = rng[v].rg-rng[u].rg;
} else break;
}
}
for( int p=; p<=maxp; p++ )
for( int t=; t<stk.size(); t++ ) {
int u=stk[t];
nxt[u][p] = nxt[nxt[u][p-]][p-];
dis[u][p] = dis[u][p-]+dis[nxt[u][p-]][p-];
}
/*
for( int t=0; t<stk.size(); t++ ) {
int u=stk[t];
fprintf( stderr, "from [%d,%d]: \n", rng[u].lf, rng[u].rg );
for( int p=0; p<=5; p++ )
fprintf( stderr, "nxt[%d]=[%d,%d] dis[%d]=%d\n", p, rng[nxt[u][p]].lf, rng[nxt[u][p]].rg, p, dis[u][p] );
fprintf( stderr, "\n" );
}
*/
int ans=n;
for( int t=; t<stk.size(); t++ ) {
int u=stk[t];
int remain=len-(rng[u].rg-rng[u].lf);
int tans = ;
for( int p=maxp; dis[u][] && dis[u][]<remain; p-- )
if( dis[u][p]<remain ) {
remain-=dis[u][p];
tans += <<p;
u=nxt[u][p];
}
tans++;
if( dis[u][]== ) continue;
fprintf( stderr, "from [%d,%d] got ans %d\n", rng[u].lf, rng[u].rg, tans );
if( tans<ans ) ans=tans;
}
printf( "%d\n", ans );
}