Centre for Gifted Education - Hanoi university of Technology

Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi.

Cho trước một tập gồm n đồ vật, mỗi đồ vật có một chi phí V_i , một giá trị W_i có số lượng vô hạn, xác định mỗi loại đồ vật cần chọn bao nhiêu sao cho tổng chi phí nhỏ hơn một ngưỡng cho trước (giới hạn của balô) và tổng giá trị cao nhất có thể được.

Input

Dòng 1: n, S (với S là giới hạn của balô)

n dòng tiếp theo: Mỗi dòng gồm 2 số V_i, W_i, m_i là chi phí và giá trị đồ vật loại i.

Output

Dòng 1: Ghi 2 số nguyên $ là tổng giá trị lớn nhất tìm được.

n dòng tiếp theo: Dòng thứ i ghi số lượng đồ vật được chọn loại i

Example

Input:
5 15
12 4 
2 2 
1 1 
1 2 
4 10 

Output:
34
0
1
0
1
3

Giới hạn:
1 <= n <= 1000
1 <= m <= 1000
1 <= Wi <= 105
1 <= Vi <= 104