// paiza POH! Lite
// result:
// http://p...content-available-to-author-only...a.jp/poh/kirishima/result/0b09cf4293d69c3f8bf6c9b316ce3aa7
// author: Leonardone @ NEETSDKASU
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n');
    var m = lines[0] ^ 0;
    var n = lines[1] ^ 0;
    var w = 0;
    var p = 0;
    var i,j;
    for(i=0; i<n; i++) {
        var line = lines[i+2] = lines[i+2].replace(/(^\s+)|(\s+$)/g, "").split(" ");
        w += line[0] ^ 0;
        p += line[1] ^ 0;
    }
    w -= m;
    var a = [];
    a[0] = [];
    for(j=0; j<=w; j++) {
        a[0][j] = 0;
    }
    for(i=0; i<n; i++) {
        a[i+1] = [];
        for(j=0; j<=w; j++) {
            if(lines[i+2][0] <= j) {
                var x = a[i][j];
                var y = a[i][j-lines[i+2][0]] + (lines[i+2][1] ^ 0);
                a[i+1][j] = (x > y) ? x : y;
            } else {
                a[i+1][j] = a[i][j];
            }
        }
    }
    console.log(p - a[n][w]);
});

Ly8gcGFpemEgUE9IISBMaXRlCi8vIHJlc3VsdDoKLy8gaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvMGIwOWNmNDI5M2Q2OWMzZjhiZjZjOWIzMTZjZTNhYTcKLy8gYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQpwcm9jZXNzLnN0ZGluLnJlc3VtZSgpOwpwcm9jZXNzLnN0ZGluLnNldEVuY29kaW5nKCd1dGY4Jyk7CnByb2Nlc3Muc3RkaW4ub24oJ2RhdGEnLCBmdW5jdGlvbiAoY2h1bmspIHsKICAgIHZhciBsaW5lcyA9IGNodW5rLnRvU3RyaW5nKCkuc3BsaXQoJ1xuJyk7CiAgICB2YXIgbSA9IGxpbmVzWzBdIF4gMDsKICAgIHZhciBuID0gbGluZXNbMV0gXiAwOwogICAgdmFyIHcgPSAwOwogICAgdmFyIHAgPSAwOwogICAgdmFyIGksajsKICAgIGZvcihpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgdmFyIGxpbmUgPSBsaW5lc1tpKzJdID0gbGluZXNbaSsyXS5yZXBsYWNlKC8oXlxzKyl8KFxzKyQpL2csICIiKS5zcGxpdCgiICIpOwogICAgICAgIHcgKz0gbGluZVswXSBeIDA7CiAgICAgICAgcCArPSBsaW5lWzFdIF4gMDsKICAgIH0KICAgIHcgLT0gbTsKICAgIHZhciBhID0gW107CiAgICBhWzBdID0gW107CiAgICBmb3Ioaj0wOyBqPD13OyBqKyspIHsKICAgICAgICBhWzBdW2pdID0gMDsKICAgIH0KICAgIGZvcihpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgYVtpKzFdID0gW107CiAgICAgICAgZm9yKGo9MDsgajw9dzsgaisrKSB7CiAgICAgICAgICAgIGlmKGxpbmVzW2krMl1bMF0gPD0gaikgewogICAgICAgICAgICAgICAgdmFyIHggPSBhW2ldW2pdOwogICAgICAgICAgICAgICAgdmFyIHkgPSBhW2ldW2otbGluZXNbaSsyXVswXV0gKyAobGluZXNbaSsyXVsxXSBeIDApOwogICAgICAgICAgICAgICAgYVtpKzFdW2pdID0gKHggPiB5KSA/IHggOiB5OwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgYVtpKzFdW2pdID0gYVtpXVtqXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGNvbnNvbGUubG9nKHAgLSBhW25dW3ddKTsKfSk7

MjUwCjUKMzUgMzY0MAozMyAyNzA2Cjk4IDk4MTAKNTcgNTQ3Mgo5NSA3NzkwIA==

250
5
35 3640
33 2706
98 9810
57 5472
95 7790