Kim cương vô hạn có cách chọn

Trên một hòn đảo có \(N\) loại kim cương, mỗi loại có vô số viên. Một viên kim cương loại \(i\) có giá trị \(a_i\) và thể tích \(b_i\). Chiếc túi của bạn có sức chứa (tổng thể tích) là \(M\).

Hãy chọn các viên kim cương (mỗi loại có thể lấy nhiều viên, hoặc không lấy) sao cho tổng thể tích không vượt quá \(M\) và tổng giá trị là lớn nhất. In ra tổng giá trị lớn nhất và số viên lấy của từng loại.

Vì có thể có nhiều phương án tối ưu, ta chỉ chấp nhận phương án duy nhất sau: trong các phương án cho giá trị lớn nhất, chọn phương án mà dãy \((c_1, c_2, \dots, c_N)\) lớn nhất theo thứ tự từ điển, trong đó \(c_i\) là số viên loại \(i\) được lấy (tức là ưu tiên \(c_1\) lớn nhất, rồi đến \(c_2\), ...).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).

Output

• Dòng đầu: tổng giá trị lớn nhất.
• Dòng thứ hai: \(N\) số nguyên \(c_1, c_2, \dots, c_N\) cách nhau bởi dấu cách.

Constraints

• \(1 \le N \le 1000\)
• \(1 \le M \le 11111\)
• \(0 \le a_i \le 10^9\)
• \(1 \le b_i \le 10^4\)

Sample Input 1

3 9
4 2
6 3
5 3

Sample Output 1

18
3 1 0

Sample Input 2

4 6
3 2
9 3
6 2
1 1

Sample Output 2

18
0 2 0 0

Explanation

Ví dụ 1: giá trị lớn nhất là \(18\), đạt được bởi \((3,1,0)\) (thể tích \(6+3\)) và cũng bởi \((0,3,0)\). Dãy \((3,1,0)\) lớn hơn theo thứ tự từ điển nên được in ra. Ví dụ 2: giá trị lớn nhất là \(18\), đạt được bằng hai viên loại 2 hoặc ba viên loại 3; chọn \(c_1 \ge 1\) không thể đạt \(18\), còn với \(c_1 = 0\) thì \(c_2 = 2\) là lớn nhất, nên in \((0,2,0,0)\).