/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/4540e9efffb1299f0915533326575d70
* author: Leonardone @ NEETSDKASU
*/
import java.io.*;
import java.lang.*;
import java.util.*;
class Main
{
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
= Integer.
parseInt(in.
readLine()); n
= Integer.
parseInt(in.
readLine());
for (i = 0; i < n; i++) {
String[] str
= in.
readLine().
split(" "); 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
]);
}
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvNDU0MGU5ZWZmZmIxMjk5ZjA5MTU1MzMzMjY1NzVkNzAKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KaW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgamF2YS51dGlsLio7CgpjbGFzcyBNYWluCnsKCQoJc3RhdGljIGludFtdW10gYSA9IG5ldyBpbnRbNTFdWzUwMDAwMV07CglzdGF0aWMgaW50W10gcSA9IG5ldyBpbnRbNTFdOwoJc3RhdGljIGludFtdIHIgPSBuZXcgaW50WzUxXTsKCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQkKCQlpbnQgbTsKCQlpbnQgbjsKCQkKCQlpbnQgdyA9IDAsIHAgPSAwOwoJCQoJCWludCBpLCBqLCB4LCB5OwoJCWludFtdIHQwLCB0MTsKCQkKCQlCdWZmZXJlZFJlYWRlciBpbiA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CgkJbSA9IEludGVnZXIucGFyc2VJbnQoaW4ucmVhZExpbmUoKSk7CgkJbiA9IEludGVnZXIucGFyc2VJbnQoaW4ucmVhZExpbmUoKSk7CgoJCWZvciAoaSA9IDA7IGkgPCBuOyBpKyspIHsKCQkJU3RyaW5nW10gc3RyID0gaW4ucmVhZExpbmUoKS5zcGxpdCgiICIpOwoJCQlxW2ldID0gSW50ZWdlci5wYXJzZUludChzdHJbMF0pOwoJCQlyW2ldID0gSW50ZWdlci5wYXJzZUludChzdHJbMV0pOwoJCQl3ICs9IHFbaV07CgkJCXAgKz0gcltpXTsKCQl9CgkJdyAtPSBtOwoJCQoJCWZvciAoaSA9IDA7IGkgPCBuOyBpKyspIHsKCQkJdDAgPSBhW2ldOwoJCQl0MSA9IGFbaSArIDFdOwoJCQlmb3IgKGogPSAwOyBqIDw9IHc7IGorKykgewoJCQkJaWYgKHFbaV0gPD0gaikgewoJCQkJCXggPSB0MFtqXTsKCQkJCQl5ID0gdDBbaiAtIHFbaV1dICsgcltpXTsKCQkJCQl0MVtqXSA9ICh4ID4geSkgPyB4IDogeTsKCQkJCX0gZWxzZSB7CgkJCQkJdDFbal0gPSB0MFtqXTsKCQkJCX0KCQkJfQoJCX0KCQkKCQlTeXN0ZW0ub3V0LnByaW50bG4ocCAtIGFbbl1bd10pOwoKCX0KfQ==