#include <bits/stdc++.h>
using namespace std ;
const int N = 30 ;
int n , b ;
int a[N] , c[N] ;
int choose[N] ;
int ans[N] ;
int res = 0 ;
void dq( int id , int cura , int curc ){
    if ( id == n ){
        if ( cura <= b && curc >= res ){
            res = curc ;
            for ( int i = 0 ; i < n ;i++ )
                ans[i] = choose[i] ;
        }
        return ;
    }
    for ( int i = 0 ; i <= 1 ; i++ ){
        choose[id] = i ;
        dq( id + 1 , cura + i*a[id] , curc + i*c[id] ) ;
    }
}
int main(){
    cin >> n >> b ;
    for ( int i = 0 ; i < n ; i++ )
        cin >> a[i] >> c[i] ;
    dq( 0 , 0 , 0 ) ;
    cout << res << endl ;
    for ( int i = 0 ; i < n ;i ++ )
        cout << ans[i] << " " ;
}