:- use_module(library(clpfd)).

main :-
	read_num(N),
        read_num(W),
	read_n_num_list(N, WeightList, ValueList),

        length(B, N),
        B ins 0..1,
        scalar_product(WeightList, B, #=<, W),
        scalar_product(ValueList, B, #=, V),
        append(B, [V], L),
        labeling([max(V)], L),
        
	write(V),
	nl,
	halt.


read_n_num_list(N, WeightList, ValueList) :-
	read_n_num_list_aux(N, [], [], WeightList, ValueList),
	!.
read_n_num_list_aux(0, WeightList, ValueList, WeightList, ValueList).
read_n_num_list_aux(Num, OldWeightList, OldValueList, WeightAccum, ValueAccum) :-
	read_num(NewWeight),
        read_num(NewValue),
	NewNum is Num - 1,
	append(OldWeightList, [NewWeight], NewWeightList),
        append(OldValueList, [NewValue], NewValueList),
	read_n_num_list_aux(NewNum, NewWeightList, NewValueList, WeightAccum, ValueAccum).

read_str(S) :-
        read_string(current_input, ' \n', '', _, S).

read_num(N) :-
	read_str(S),
	number_string(N, S).

:- main.
