/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/050e7c0556cbbf5791a5018fd30b558f
* 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;
int *t0, *t1;
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++) {
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];
}
}
}
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvMDUwZTdjMDU1NmNiYmY1NzkxYTUwMThmZDMwYjU1OGYKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBhWzUxXVs1MDAwMDFdOwppbnQgcVs1MV07CmludCByWzUxXTsKCmludCBtYWluKHZvaWQpIHsKCQoJaW50IG07CglpbnQgbjsKCQoJaW50IHcgPSAwLCBwID0gMDsKCQoJaW50IGksIGosIHgsIHk7CglpbnQgKnQwLCAqdDE7CgkKCQoJc2NhbmYoIiVkIiwgJm0pOwoJc2NhbmYoIiVkIiwgJm4pOwoJCglmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJc2NhbmYoIiVkICVkIiwgJnFbaV0sICZyW2ldKTsKCQl3ICs9IHFbaV07CgkJcCArPSByW2ldOwoJfQoJdyAtPSBtOwoJCglmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJdDAgPSBhW2ldOwoJCXQxID0gYVtpICsgMV07CgkJZm9yIChqID0gMDsgaiA8PSB3OyBqKyspIHsKCQkJaWYgKHFbaV0gPD0gaikgewoJCQkJeCA9IHQwW2pdOwoJCQkJeSA9IHQwW2ogLSBxW2ldXSArIHJbaV07CgkJCQl0MVtqXSA9ICh4ID4geSkgPyB4IDogeTsKCQkJfSBlbHNlIHsKCQkJCXQxW2pdID0gdDBbal07CgkJCX0KCQl9Cgl9CgkKCXByaW50ZigiJWRcbiIsIHAgLSBhW25dW3ddKTsKCQoJcmV0dXJuIDA7CQp9