Cho cái túi chứa được trọng lượng tối đa là w. Có n đồ vật, đồ vật thứ i có khối lượng a[i] và giá trị c[i], 1<= i <=n. Tìm cách xếp đồ vật vào túi sao cho đạt giá trị lớn nhất. (số lượng 1 vật có thể chọn 1 hoặc không chọn)

Input:

dòng 1: số đồ vật(n), trọng lượng tối đa (W).

dòng 2: khối lượng của các đồ vật (A[i]…a[n]).

dòng 3: giá trị của các đồ vật (C[i]…c[n]).

Output:

dòng 1: các đồ vật được chọn

dòng 2: Tổng giá trị cái tui sau khi chọn vật, trọng lượng tối đa (w)

Vd:

Input:

4 10

7 4 3 2

9 4 3 1

output:

3 1

12 10