Ngày 12 tháng 1 năm 2010, một trận động đất lớn chưa từng có tại Haiti trong 200 năm qua đã làm rung chuyển toàn bộ quốc gia này, khiến nhiều tòa nhà bị sụp đổ, trong đó có dinh tổng thống. Trận động đất có cường độ 7 độ Richter và nhanh chóng kéo theo hai dư chấn với cường độ 5,9 và 5,5 độ Richter. Tâm chấn nằm cách thủ đô Port-au-Prince 15 km về phía tây nam và nằm ở độ sâu 8 km dưới mặt biển.

Hai cựu Tổng thống Hoa Kỳ Bush (phải) và Clinton (trái) đứng trước dinh tổng thống bị sụp đổ trong trận động đất.

Hai cựu tổng thống Bush và Clinton đã được Tổng thống Barack Obama yêu cầu lãnh đạo chiến dịch gây quỹ và giám sát những nỗ lực tái thiết dài hạn và những nỗ lực cứu trợ tại quốc gia nghèo nhất Tây Bán cầu này. Quỹ bất vụ lợi Clinton-Bush cho Haiti đã thu được \(n\) triệu đô la cho những nỗ lực cứu trợ. Công việc cần phải làm ngay lúc này là phân bổ tất cả \(n\) triệu đô la cho \(m\) thành phố của Haiti, thành phố nào cũng sẽ nhận được cứu trợ (số tiền là số nguyên dương).

Theo thông tin khảo sát được của Liên Hiệp Quốc thì thành phố thứ \(i\) có mức độ ảnh hưởng của động đất là \(d_i\). Gọi \(t_1, t_2, \ldots, t_m\) là số tiền mà các thành phố nhận được (\(\sum t_i = n\)); gọi \(s_i\) là số lượng các thành phố được nhận nhiều tiền hơn thành phố \(i\) thì sự bất bình của thành phố \(i\) sẽ là \(d_i \cdot s_i\). Thật là khó, hai cựu tổng thống Bush và Clinton tìm đến các bạn đã đạt giải cao trong kỳ thi VNOI tìm cách phân bổ để tổng sự bất bình của các thành phố là nhỏ nhất.

Yêu cầu: Cho \(m, n\) và \(d_1, d_2, \ldots, d_m\), hãy tìm cách phân bổ để tổng sự bất bình của \(m\) thành phố là ít nhất.

Input

• Dòng 1: gồm 2 số nguyên \(m, n\) \((0 < m \le 30, m \le n \le 10^4)\).
• Dòng 2: gồm \(m\) số nguyên \(d_1, d_2, \ldots, d_m\) \((0 \le d_i \le 10^9)\).

Output

• Dòng 1: tổng sự bất bình nhỏ nhất tìm được.
• Dòng 2: gồm \(m\) số nguyên dương \(t_1, t_2, \ldots, t_m\) là số tiền mà các thành phố nhận được.

Example

3 5
100 200 300

200
1 2 2