#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rafturi.in");
ofstream fout("rafturi.out");

struct book_boiii {
	int dulap, raft, minim = 0;
}books[10050];

int C, N, maxim = 0;

void Solve()
{
	for (int i = 1; i <= maxim; ++i){
		int x = books[i-1].minim + books[i].raft;
		int y = books[i-2].minim + max(books[i-1].raft, books[i].raft);
		int z = books[i-3].minim + max(max(books[i-2].raft, books[i-1].raft), books[i].raft);
		books[i].minim = min(min(x, y), z);
	}
}

void Read()
{
	fin >> C >> N;
	for (int i = 0; i < N; ++i){
		int d, r;
		fin >> d >> r;
		books[d].dulap = d;
		books[d].raft = r;
		maxim = max(maxim, d);
	}
}

void Write()
{
	fout << books[maxim].minim;
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}