/****************0-N背包问题******************

 * 有n个物体装入容量为c的背包，每一个物体有一个体积

 * 和一个价值，所装入的物体体积之和不大于背包体积，

 * 且每个物体可以多次装入，即每个物体有很多个（与0-1

 * 背包问题的区别），求装入的最大价值？

 * *****************************************/

/********************************************

 * Author:ChengSong

 * Time:2015/12/29 22:24

 * language:C++

 * alogrithm: Dynamic Programing(动态规划)

 * *****************************************/

#include<iostream>

#include<cstdlib>

#include<cmath>

using namespace std;

int knapsack0N(int goodsnum,int capacity,int *weight,int *value,int **result,int *count){

    for(int i=;i<goodsnum+;++i)result[i][] = ;//容量为0的时候result[i][0] =0

    for(int j=;j<capacity+;++j)result[][j] = ;//没有物体时候result[0][j] = 0

    /*递归求解结果集result*/

    for(int i=;i<goodsnum+;++i)

        for(int j=;j<capacity+;++j)

        {

            if(weight[i]>j){//当第i个物体的重量weight[i]大于背包重量j时

                result[i][j] = result[i-][j];

            }

            else{//当物体的重量小于等于背包重量时

                int max_k = j/weight[i];//max_k为当前背包容量为j时最多可装入物体i的个数

                int t = result[i-][j];

                for(int k=;k<max_k+;++k){//循环求解出result[i-1][j]与result[i-1][j-k*weight[i]]+k*value[i]的最大的一个（k=1...max_k）

                    if(t<result[i-][j-k*weight[i]]+k*value[i]){

                        t = result[i-][j-k*weight[i]]+k*value[i];

                    }

                }

                result[i][j] = t;//当前t 为result[i-1][j]与result[i-1][j-k*weight[i]]+k*value[i]的最大的一个(k=1...max_k)

            }

        }

    return result[goodsnum][capacity];//返回最后结果:容量为capacityd背包装入goodsnum种物体的最大值

}

int main(){

    int goodsnum,capacity;//物体个数与背包容量

    cin>>goodsnum>>capacity;

    int *count = new int[goodsnum+];

    for(int i=;i<goodsnum+;++i)

        count[i] = ;//每个物体放入的个数，初始化为0

    int *weight = new int[goodsnum+];

    int *value = new int[goodsnum+];

    int **result = new int*[goodsnum+];//结果集，result[i][j]表示有i类物体放入容量为j的背包内的最大价值

    for(int i=;i<goodsnum+;i++)

        result[i] = new int[capacity+];

    for(int i=;i<goodsnum+;++i){

        cin>>weight[i]>>value[i];

    }

    cout<<knapsack0N(goodsnum,capacity,weight,value,result,count)<<endl;

    /*该循环用来计算每个物体装入的个数*/

    for(int i=goodsnum;i>;){

        if(result[i][capacity]==result[i-][capacity])//该条件下物体i不装入，count[i]不变，i--

            i--;

        else{

            //该条件下物体i可以装入数目增加一个,i不变，在进入循环，看看i物体是否还能在装入

            count[i]++;

            capacity -= weight[i];

        }

    }

    //将装入个数不为0的物体输出，并输出该物体装入的个数

    for(int i=;i<goodsnum+;i++){

        if(count[i]!=)

            cout<<i<<" "<<count[i]<<endl;

    }

    return ;

}