#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
const int maxn = 1009; const dint inf = 0x3f3f3f3f3f3f3f3fll;
int n, m, ca[maxn], cb[maxn], ta, tb; dint f[maxn][maxn][5];
#define upMin(a,b) {
if (a > b)
a = b;
}
dint dp() { memset(f, 0x3f, sizeof(f)); if (ta) f[1][0][0] = ca[0] * n; if (tb) f[0][1][2] = cb[0] * n; for (int i = 0; i <= ta; ++ i) for (int j = 0; j <= tb; ++ j) if (n - i - j > 0) { int cc(n - i - j); if (f[i][j][0] < inf) { if (i < ta) upMin(f[i + 1][j][1], f[i][j][0] + ca[i] * cc); if (j < tb) upMin(f[i][j + 1][2], f[i][j][0] + cb[j] * cc); } if (f[i][j][1] < inf) { if (j < tb) upMin(f[i][j + 1][2], f[i][j][1] + cb[j] * cc); } if (f[i][j][2] < inf) { if (i < ta) upMin(f[i + 1][j][0], f[i][j][2] + ca[i] * cc); if (j < tb) upMin(f[i][j + 1][3], f[i][j][2] + cb[j] * cc); } if (f[i][j][3] < inf) { if (i < ta) upMin(f[i + 1][j][0], f[i][j][3] + ca[i] * cc); } } dint ans(inf); for (int i = 0; i <= n; ++ i) for (int j = 0; j < 4; ++ j) upMin(ans, f[i][n - i][j]); return ans; }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
scanf("%d%d", &n, &m);
ta = tb = 0;
for (int i = 0; i < m; ++ i) {
int co, ty;
scanf("%d%d", &co, &ty);
if (!ty)
ca[ta ++] = co;
else
cb[tb ++] = co;
}
sort(ca, ca + ta);
sort(cb, cb + tb);
printf(lld "\n", dp());
}