1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXM = 20001;
int dp[MAXM];
int copydp[MAXM];
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int a, b; cin >> a >> b;
        int current = b, cb = b, ca = a;
        for (; current <= m; current += cb) {
            for (int j = current; j <= m; ++j) {
                copydp[j] = max(copydp[j], dp[j-current] + ca);
            }
            cb = floor(cb * 1.07);
            ca += a;
        }
        memcpy(dp, copydp, sizeof(int) * (m+1));
    }
    cout << *(max_element(dp, dp+m+1)) << endl;
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX