/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/e0dc73382fe071c8016bf5fdd884277b
* author: Leonardone @ NEETSDKASU
*/
#include <stdio.h>
#include <stdlib.h>
int a[51][500001];
int q[51];
int r[51];
int main(void) {
int m;
int n;
int w = 0, p = 0;
int i, j, x, y;
for (i = 0; i < n; i++) {
scanf("%d %d", &q
[i
], &r
[i
]); w += q[i];
p += r[i];
}
w -= m;
for (i = 0; i < n; i++) {
for (j = 0; j <= w; j++) {
if (q[i] <= j) {
x = a[i][j];
y = a[i][j - q[i]] + r[i];
a[i + 1][j] = (x > y) ? x : y;
} else {
a[i + 1][j] = a[i][j];
}
}
}
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvZTBkYzczMzgyZmUwNzFjODAxNmJmNWZkZDg4NDI3N2IKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBhWzUxXVs1MDAwMDFdOwppbnQgcVs1MV07CmludCByWzUxXTsKCmludCBtYWluKHZvaWQpIHsKCQoJaW50IG07CglpbnQgbjsKCQoJaW50IHcgPSAwLCBwID0gMDsKCQoJaW50IGksIGosIHgsIHk7CgkKCXNjYW5mKCIlZCIsICZtKTsKCXNjYW5mKCIlZCIsICZuKTsKCQoJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCXNjYW5mKCIlZCAlZCIsICZxW2ldLCAmcltpXSk7CgkJdyArPSBxW2ldOwoJCXAgKz0gcltpXTsKCX0KCXcgLT0gbTsKCQoJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCWZvciAoaiA9IDA7IGogPD0gdzsgaisrKSB7CgkJCWlmIChxW2ldIDw9IGopIHsKCQkJCXggPSBhW2ldW2pdOwoJCQkJeSA9IGFbaV1baiAtIHFbaV1dICsgcltpXTsKCQkJCWFbaSArIDFdW2pdID0gKHggPiB5KSA/IHggOiB5OwoJCQl9IGVsc2UgewoJCQkJYVtpICsgMV1bal0gPSBhW2ldW2pdOwoJCQl9CgkJfQoJfQoJCglwcmludGYoIiVkXG4iLCBwIC0gYVtuXVt3XSk7CgkKCXJldHVybiAwOwkKfQ==