#include <iostream>
#include <vector>

using namespace std;

int bpSum(vector<int> val, vector<int> wt, int W) {

    int n = val.size() ;
    int mat[n+1][W+1];

    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                mat[i][j] = 0;
            } else if (j <= wt[i-1]) {
                mat[i][j] = mat[i-1][j];
            } else {
                mat[i][j] = max( (val[i] + mat[i-1][j - wt[i]]), mat[i-1][j] );
            }
        }
    }

    return mat[n][W];
}

int main()
{
    int n,x,W;
    vector<int> val, wt;
    cin>>n >> W;
    for(int i = 0; i < n; i++) {
        cin >> x;
        wt.push_back(x);
        cin >> x;
        val.push_back(x);
    }
    for(int i = 0; i < n; i++) {
            cout << val[i] << " ";
    }
    cout << endl;
     for(int i = 0; i < n; i++) {
            cout << wt[i] << " ";
    }
    cout << endl;
    cout << "Sum is: " << bpSum(val,wt,W) << endl;
    return 0;
}