rafturi

#include <cstdio>
#include <algorithm>
#define NMAX 10003
#define MAXV 2000000003
using namespace std;
long long c,n,x,y,sum,i,nr,j,h;
long long m[NMAX];
long long v[NMAX];

int main()
{
    freopen("rafturi.in","r",stdin);
    freopen("rafturi.out","w",stdout);
    scanf("%lli%lli",&c,&n);
    for(i=1;i<=n;++i)
    {
        scanf("%lli %lli",&x,&y);
        v[x]=max(v[x],y);
    }
    m[0]=0;
    for(i=1;i<=c;++i)
    {
        m[i]=MAXV;
        h=v[i];

        if(m[i-1]+h<m[i])
            m[i]=m[i-1]+h;

        for(j=i-1;j>i-3 && j>0;--j)
        {
            if(h<v[j])
                h=v[j];
            if(m[j-1]+h<m[i])
                m[i]=m[j-1]+h;
        }
    }
    printf("%lli ",m[c]);

    return 0;
}