/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/1321743659685576f508f1ceb4e2e71f
* author: Leonardone @ NEETSDKASU
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _data {
int q;
int r;
} DATA, *PDATA;
int m, n;
DATA data[50];
int min = 250000000;
DATA temp[5][1024];
int sort_q(void *a, void *b) {
PDATA pa = (PDATA)a;
PDATA pb = (PDATA)b;
return pb->q - pa->q;
}
void foo(int sum_q, int sum_r, int k) {
int i, q, r;
for (i = 0; i < 1024 && temp[k][i].q > 0; i++) {
q = sum_q + temp[k][i].q;
r = sum_r + temp[k][i].r;
if (q >= m) {
if (r < min) {
min = r;
}
} else if (k < 4) {
foo(q, r, k + 1);
}
}
}
int main(void) {
int i, j, k;
for (i = 0; i < n; i++) {
scanf("%d %d", &data
[i
].
q, &data
[i
].
r); }
for (i = 0; i < 1024; i++) {
for (j = 0; j < 10; j++) {
if ((i >> j) & 1) {
for (k = 0; k < 5; k++) {
temp[k][i].q += data[j + k * 10].q;
temp[k][i].r += data[j + k * 10].r;
}
}
}
}
for (i = 0; i < 5; i++) {
qsort(temp
[i
], 1024, sizeof(DATA
), sort_q
); }
foo(0, 0, 0);
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvMTMyMTc0MzY1OTY4NTU3NmY1MDhmMWNlYjRlMmU3MWYKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IF9kYXRhIHsKCWludCBxOwoJaW50IHI7Cn0gREFUQSwgKlBEQVRBOwoKaW50IG0sIG47CkRBVEEgZGF0YVs1MF07CgppbnQgbWluID0gMjUwMDAwMDAwOwoKREFUQSB0ZW1wWzVdWzEwMjRdOwoKaW50IHNvcnRfcSh2b2lkICphLCB2b2lkICpiKSB7CglQREFUQSBwYSA9IChQREFUQSlhOwoJUERBVEEgcGIgPSAoUERBVEEpYjsKCXJldHVybiBwYi0+cSAtIHBhLT5xOwp9Cgp2b2lkIGZvbyhpbnQgc3VtX3EsIGludCBzdW1fciwgaW50IGspIHsKCWludCBpLCBxLCByOwoJCglmb3IgKGkgPSAwOyBpIDwgMTAyNCAmJiB0ZW1wW2tdW2ldLnEgPiAwOyBpKyspIHsKCQlxID0gc3VtX3EgKyB0ZW1wW2tdW2ldLnE7CgkJciA9IHN1bV9yICsgdGVtcFtrXVtpXS5yOwoJCWlmIChxID49IG0pIHsKCQkJaWYgKHIgPCBtaW4pIHsKCQkJCW1pbiA9IHI7CgkJCX0KCQl9IGVsc2UgaWYgKGsgPCA0KSB7CgkJCWZvbyhxLCByLCBrICsgMSk7CgkJfQoJfQp9CgppbnQgbWFpbih2b2lkKSB7CglpbnQgaSwgaiwgazsKCQoJc2NhbmYoIiVkIiwgJm0pOwoJc2NhbmYoIiVkIiwgJm4pOwoJCglmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJc2NhbmYoIiVkICVkIiwgJmRhdGFbaV0ucSwgJmRhdGFbaV0ucik7Cgl9CgkKCWZvciAoaSA9IDA7IGkgPCAxMDI0OyBpKyspIHsKCQlmb3IgKGogPSAwOyBqIDwgMTA7IGorKykgewoJCQlpZiAoKGkgPj4gaikgJiAxKSB7CgkJCQlmb3IgKGsgPSAwOyBrIDwgNTsgaysrKSB7CgkJCQkJdGVtcFtrXVtpXS5xICs9IGRhdGFbaiArIGsgKiAxMF0ucTsKCQkJCQl0ZW1wW2tdW2ldLnIgKz0gZGF0YVtqICsgayAqIDEwXS5yOwoJCQkJfQoJCQl9CgkJfQogCX0KCQoJZm9yIChpID0gMDsgaSA8IDU7IGkrKykgewoJCXFzb3J0KHRlbXBbaV0sIDEwMjQsIHNpemVvZihEQVRBKSwgc29ydF9xKTsKCX0KCglmb28oMCwgMCwgMCk7CgkKCXByaW50ZigiJWRcbiIsIG1pbik7CgkKCXJldHVybiAwOwp9Cg==