/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/327fdfad3b495e0501dd024b36334c29
* author: Leonardone @ NEETSDKASU
*/
import java.io.*;
import java.lang.*;
import java.util.*;
class Main
{
static int parseInt
(String str
) { int len = str.length();
int n = 0;
for (int i = 0; i < len; i++) {
n = n * 10 + (int)(str.charAt(i) - '0');
}
return n;
}
static int[][] a = new int[51][500001];
static int[] q = new int[51];
static int[] r = new int[51];
{
int m;
int n;
int w = 0, p = 0;
int i, j, x, y;
int[] t0, t1;
m = parseInt(in.readLine());
n = parseInt(in.readLine());
for (i = 0; i < n; i++) {
String[] str
= in.
readLine().
split(" "); q[i] = parseInt(str[0]);
r[i] = parseInt(str[1]);
w += q[i];
p += r[i];
}
w -= m;
for (i = 0; i < n; i++) {
t0 = a[i];
t1 = a[i + 1];
for (j = 0; j <= w; j++) {
if (q[i] <= j) {
x = t0[j];
y = t0[j - q[i]] + r[i];
t1[j] = (x > y) ? x : y;
} else {
t1[j] = t0[j];
}
}
}
System.
out.
println(p
- a
[n
][w
]);
}
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvMzI3ZmRmYWQzYjQ5NWUwNTAxZGQwMjRiMzYzMzRjMjkKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KaW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgamF2YS51dGlsLio7CgpjbGFzcyBNYWluCnsKCXN0YXRpYyBpbnQgcGFyc2VJbnQoU3RyaW5nIHN0cikgewoJCWludCBsZW4gPSBzdHIubGVuZ3RoKCk7CgkJaW50IG4gPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbGVuOyBpKyspIHsKCQkJbiA9IG4gKiAxMCArIChpbnQpKHN0ci5jaGFyQXQoaSkgLSAnMCcpOwoJCX0KCQlyZXR1cm4gbjsKCX0KCQoJc3RhdGljIGludFtdW10gYSA9IG5ldyBpbnRbNTFdWzUwMDAwMV07CglzdGF0aWMgaW50W10gcSA9IG5ldyBpbnRbNTFdOwoJc3RhdGljIGludFtdIHIgPSBuZXcgaW50WzUxXTsKCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQkKCQlpbnQgbTsKCQlpbnQgbjsKCQkKCQlpbnQgdyA9IDAsIHAgPSAwOwoJCQoJCWludCBpLCBqLCB4LCB5OwoJCWludFtdIHQwLCB0MTsKCQkKCQlCdWZmZXJlZFJlYWRlciBpbiA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CgkJbSA9IHBhcnNlSW50KGluLnJlYWRMaW5lKCkpOwoJCW4gPSBwYXJzZUludChpbi5yZWFkTGluZSgpKTsKCgkJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCQlTdHJpbmdbXSBzdHIgPSBpbi5yZWFkTGluZSgpLnNwbGl0KCIgIik7CgkJCXFbaV0gPSBwYXJzZUludChzdHJbMF0pOwoJCQlyW2ldID0gcGFyc2VJbnQoc3RyWzFdKTsKCQkJdyArPSBxW2ldOwoJCQlwICs9IHJbaV07CgkJfQoJCXcgLT0gbTsKCQkKCQlmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJCXQwID0gYVtpXTsKCQkJdDEgPSBhW2kgKyAxXTsKCQkJZm9yIChqID0gMDsgaiA8PSB3OyBqKyspIHsKCQkJCWlmIChxW2ldIDw9IGopIHsKCQkJCQl4ID0gdDBbal07CgkJCQkJeSA9IHQwW2ogLSBxW2ldXSArIHJbaV07CgkJCQkJdDFbal0gPSAoeCA+IHkpID8geCA6IHk7CgkJCQl9IGVsc2UgewoJCQkJCXQxW2pdID0gdDBbal07CgkJCQl9CgkJCX0KCQl9CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKHAgLSBhW25dW3ddKTsKCgl9Cn0=