/* paiza POH! Lite
* result:
* http://p...content-available-to-author-only...a.jp/poh/kirishima/result/722db88b267db22d802af06cd4c39b7e
* 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);
} else {
return;
}
}
}
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;
}
}
temp[i][l].q = 0;
temp[i][l].r = 0;
s[i] = l + 1;
}
foo(0, 0, 0);
return 0;
}
LyogcGFpemEgUE9IISBMaXRlCiAqIHJlc3VsdDoKICogaHR0cDovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuanAvcG9oL2tpcmlzaGltYS9yZXN1bHQvNzIyZGI4OGIyNjdkYjIyZDgwMmFmMDZjZDRjMzliN2UKICogYXV0aG9yOiBMZW9uYXJkb25lIEAgTkVFVFNES0FTVQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IF9kYXRhIHsKCWludCBxOwoJaW50IHI7Cn0gREFUQSwgKlBEQVRBOwoKaW50IG0sIG47CkRBVEEgZGF0YVs1MF07CgppbnQgbWluID0gMjUwMDAwMDAwOwoKREFUQSB0ZW1wWzVdWzEwMjRdOwppbnQgc1s1XTsKCmludCBzb3J0X3Eodm9pZCAqYSwgdm9pZCAqYikgewoJUERBVEEgcGEgPSAoUERBVEEpYTsKCVBEQVRBIHBiID0gKFBEQVRBKWI7CglyZXR1cm4gcGItPnEgLSBwYS0+cTsKfQoKdm9pZCBmb28oaW50IHN1bV9xLCBpbnQgc3VtX3IsIGludCBrKSB7CglpbnQgaSwgcSwgcjsKCQoJZm9yIChpID0gMDsgaSA8IHNba10gJiYgdGVtcFtrXVtpXS5xID4gMDsgaSsrKSB7CgkJcSA9IHN1bV9xICsgdGVtcFtrXVtpXS5xOwoJCXIgPSBzdW1fciArIHRlbXBba11baV0ucjsKCQlpZiAocSA+PSBtKSB7CgkJCWlmIChyIDwgbWluKSB7CgkJCQltaW4gPSByOwoJCQl9CgkJfSBlbHNlIGlmIChrIDwgNCkgewoJCQlmb28ocSwgciwgayArIDEpOwoJCX0gZWxzZSB7CgkJCXJldHVybjsKCQl9Cgl9Cn0KCmludCBtYWluKHZvaWQpIHsKCWludCBpLCBqLCBrLCBsOwoJCglzY2FuZigiJWQiLCAmbSk7CglzY2FuZigiJWQiLCAmbik7CgkKCWZvciAoaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlzY2FuZigiJWQgJWQiLCAmZGF0YVtpXS5xLCAmZGF0YVtpXS5yKTsKCX0KCQoJZm9yIChpID0gMDsgaSA8IDEwMjQ7IGkrKykgewoJCWZvciAoaiA9IDA7IGogPCAxMDsgaisrKSB7CgkJCWlmICgoaSA+PiBqKSAmIDEpIHsKCQkJCWZvciAoayA9IDA7IGsgPCA1OyBrKyspIHsKCQkJCQl0ZW1wW2tdW2ldLnEgKz0gZGF0YVtqICsgayAqIDEwXS5xOwoJCQkJCXRlbXBba11baV0uciArPSBkYXRhW2ogKyBrICogMTBdLnI7CgkJCQl9CgkJCX0KCQl9CiAJfQoJCglmb3IgKGkgPSAwOyBpIDwgNTsgaSsrKSB7CgkJcXNvcnQodGVtcFtpXSwgMTAyNCwgc2l6ZW9mKERBVEEpLCBzb3J0X3EpOwoJfQoJCglmb3IgKGkgPSAwOyBpIDwgNTsgaSsrKSB7CgkJayA9IGwgPSAwOwoJCWZvciAoaiA9IDA7IGogPCAxMDI0OyBqKyspIHsKCQkJaWYgKHRlbXBbaV1bal0ucSA9PSB0ZW1wW2ldW2tdLnEpIHsKCQkJCWlmICh0ZW1wW2ldW2pdLnIgPCB0ZW1wW2ldW2tdLnIpIHsKCQkJCQlrID0gajsKCQkJCX0KCQkJfSBlbHNlIHsKCQkJCXRlbXBbaV1bbF0gPSB0ZW1wW2ldW2tdOwoJCQkJbCsrOwoJCQkJayA9IGo7CgkJCX0KCQl9CgkJdGVtcFtpXVtsXS5xID0gMDsKCQl0ZW1wW2ldW2xdLnIgPSAwOwoJCXNbaV0gPSBsICsgMTsKCX0KCglmb28oMCwgMCwgMCk7CgkKCXByaW50ZigiJWRcbiIsIG1pbik7CgkKCXJldHVybiAwOwp9Cg==