/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/bd6247b2711601bd7dc2ce4af23e8109
* 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 s[5];
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 < s[k] && 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, l;
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
); }
for (i = 0; i < 5; i++) {
k = l = 0;
for (j = 0; j < 1024; j++) {
if (temp[i][j].q == temp[i][k].q) {
if (temp[i][j].r < temp[i][k].r) {
k = j;
}
} else {
temp[i][l] = temp[i][k];
l++;
k = j;
}
}
s[i] = l;
}
foo(0, 0, 0);
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvYmQ2MjQ3YjI3MTE2MDFiZDdkYzJjZTRhZjIzZTgxMDkKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IF9kYXRhIHsKCWludCBxOwoJaW50IHI7Cn0gREFUQSwgKlBEQVRBOwoKaW50IG0sIG47CkRBVEEgZGF0YVs1MF07CgppbnQgbWluID0gMjUwMDAwMDAwOwoKREFUQSB0ZW1wWzVdWzEwMjRdOwppbnQgc1s1XTsKCmludCBzb3J0X3Eodm9pZCAqYSwgdm9pZCAqYikgewoJUERBVEEgcGEgPSAoUERBVEEpYTsKCVBEQVRBIHBiID0gKFBEQVRBKWI7CglyZXR1cm4gcGItPnEgLSBwYS0+cTsKfQoKdm9pZCBmb28oaW50IHN1bV9xLCBpbnQgc3VtX3IsIGludCBrKSB7CglpbnQgaSwgcSwgcjsKCQoJZm9yIChpID0gMDsgaSA8IHNba10gJiYgdGVtcFtrXVtpXS5xID4gMDsgaSsrKSB7CgkJcSA9IHN1bV9xICsgdGVtcFtrXVtpXS5xOwoJCXIgPSBzdW1fciArIHRlbXBba11baV0ucjsKCQlpZiAocSA+PSBtKSB7CgkJCWlmIChyIDwgbWluKSB7CgkJCQltaW4gPSByOwoJCQl9CgkJfSBlbHNlIGlmIChrIDwgNCkgewoJCQlmb28ocSwgciwgayArIDEpOwoJCX0KCX0KfQoKaW50IG1haW4odm9pZCkgewoJaW50IGksIGosIGssIGw7CgkKCXNjYW5mKCIlZCIsICZtKTsKCXNjYW5mKCIlZCIsICZuKTsKCQoJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCXNjYW5mKCIlZCAlZCIsICZkYXRhW2ldLnEsICZkYXRhW2ldLnIpOwoJfQoJCglmb3IgKGkgPSAwOyBpIDwgMTAyNDsgaSsrKSB7CgkJZm9yIChqID0gMDsgaiA8IDEwOyBqKyspIHsKCQkJaWYgKChpID4+IGopICYgMSkgewoJCQkJZm9yIChrID0gMDsgayA8IDU7IGsrKykgewoJCQkJCXRlbXBba11baV0ucSArPSBkYXRhW2ogKyBrICogMTBdLnE7CgkJCQkJdGVtcFtrXVtpXS5yICs9IGRhdGFbaiArIGsgKiAxMF0ucjsKCQkJCX0KCQkJfQoJCX0KIAl9CgkKCWZvciAoaSA9IDA7IGkgPCA1OyBpKyspIHsKCQlxc29ydCh0ZW1wW2ldLCAxMDI0LCBzaXplb2YoREFUQSksIHNvcnRfcSk7Cgl9CgkKCWZvciAoaSA9IDA7IGkgPCA1OyBpKyspIHsKCQlrID0gbCA9IDA7CgkJZm9yIChqID0gMDsgaiA8IDEwMjQ7IGorKykgewoJCQlpZiAodGVtcFtpXVtqXS5xID09IHRlbXBbaV1ba10ucSkgewoJCQkJaWYgKHRlbXBbaV1bal0uciA8IHRlbXBbaV1ba10ucikgewoJCQkJCWsgPSBqOwoJCQkJfQoJCQl9IGVsc2UgewoJCQkJdGVtcFtpXVtsXSA9IHRlbXBbaV1ba107CgkJCQlsKys7CgkJCQlrID0gajsKCQkJfQoJCX0KCQlzW2ldID0gbDsKCX0KCglmb28oMCwgMCwgMCk7CgkKCXByaW50ZigiJWRcbiIsIG1pbik7CgkKCXJldHVybiAwOwp9Cg==