/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/196d3049d791ab74388a4566b13dd881
* author: Leonardone @ NEETSDKASU
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _data {
int q;
int r;
} DATA, *PDATA;
int a[51][500001];
DATA data[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", &data
[i
].
q, &data
[i
].
r); w += data[i].q;
p += data[i].r;
}
w -= m;
for (i = 0; i < n; i++) {
for (j = 0; j <= w; j++) {
if (data[i].q <= j) {
x = a[i][j];
y = a[i][j - data[i].q] + data[i].r;
a[i + 1][j] = (x > y) ? x : y;
} else {
a[i + 1][j] = a[i][j];
}
}
}
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvMTk2ZDMwNDlkNzkxYWI3NDM4OGE0NTY2YjEzZGQ4ODEKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IF9kYXRhIHsKCWludCBxOwoJaW50IHI7Cn0gREFUQSwgKlBEQVRBOwoKaW50IGFbNTFdWzUwMDAwMV07CkRBVEEgZGF0YVs1MV07CgppbnQgbWFpbih2b2lkKSB7CgkKCWludCBtOwoJaW50IG47CgkKCWludCB3ID0gMCwgcCA9IDA7CgkKCWludCBpLCBqLCB4LCB5OwoJCglzY2FuZigiJWQiLCAmbSk7CglzY2FuZigiJWQiLCAmbik7CgkKCWZvciAoaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlzY2FuZigiJWQgJWQiLCAmZGF0YVtpXS5xLCAmZGF0YVtpXS5yKTsKCQl3ICs9IGRhdGFbaV0ucTsKCQlwICs9IGRhdGFbaV0ucjsKCX0KCXcgLT0gbTsKCQoJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCWZvciAoaiA9IDA7IGogPD0gdzsgaisrKSB7CgkJCWlmIChkYXRhW2ldLnEgPD0gaikgewoJCQkJeCA9IGFbaV1bal07CgkJCQl5ID0gYVtpXVtqIC0gZGF0YVtpXS5xXSArIGRhdGFbaV0ucjsKCQkJCWFbaSArIDFdW2pdID0gKHggPiB5KSA/IHggOiB5OwoJCQl9IGVsc2UgewoJCQkJYVtpICsgMV1bal0gPSBhW2ldW2pdOwoJCQl9CgkJfQoJfQoJCglwcmludGYoIiVkXG4iLCBwIC0gYVtuXVt3XSk7CgkKCXJldHVybiAwOwkKfQ==