记录编号	42573	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2012-09-26 16:11:54	内存使用	0.34 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100 + 10, INF = 0x7ffffff;
int n, m, a[N], b[N], s;
int f[N][N], l, r, u;
int g(int d) {
    for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            f[i][j] = -INF;
    f[0][0] = 0;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=m; j++)
            for(int k=0; k<=j; k++)
                if(d - a[i] * k >= 0)
                    f[i][j] = max(f[i][j],
                f[i-1][j-k] + (d - a[i] * k) / b[i]);
    return f[n][m];
}
int main() {
    freopen("time.in", "r", stdin);
    freopen("time.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d %d", a+i, b+i);
    r = 1; do {
        r *= 2;
    } while(g(r) <= m);
    l = r - r / 2; do {
        if(g(u = (l + r) / 2) < m)
            l = u + 1;
        else r = (s = u) - 1;
    } while(l <= r);
    printf("%d\n", s);
    return 0;
}