Lập lịch khởi hành

Có $n$ chuyến bay phải khởi hành trong hôm nay. Ban đầu, chuyến bay thứ $i$ được lên lịch khởi hành vào phút thứ $i$ của ngày.

Do sự cố kỹ thuật, không chuyến bay nào có thể khởi hành trong $k$ phút đầu tiên của ngày. Vì vậy cần lập lịch khởi hành mới.

Toàn bộ $n$ chuyến bay giờ phải khởi hành vào các phút khác nhau nằm trong khoảng từ phút thứ $k+1$ đến phút thứ $k+n$ (bao gồm hai đầu mút). Thứ tự các chuyến bay trong lịch mới có thể khác thứ tự ban đầu, nhưng có một ràng buộc: không chuyến bay nào được khởi hành sớm hơn thời điểm nó được lên lịch ban đầu. Nghĩa là chuyến bay $i$ chỉ có thể khởi hành vào phút $\ge i$.

Mỗi phút bị hoãn của chuyến bay thứ $i$ tốn $c_i$ đơn vị chi phí. Nếu chuyến bay $i$ khởi hành vào phút $t_i$ thì chi phí hoãn của nó là $c_i·(t_i-i)$.

Hãy tìm cách xếp lịch khởi hành sao cho tổng chi phí là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.

Dữ liệu ra

• Dòng đầu ghi tổng chi phí hoãn nhỏ nhất.
• Dòng thứ hai ghi $n$ số nguyên phân biệt $t_1,t_2,\dots ,t_n$, trong đó $t_i$ là phút chuyến bay thứ $i$ khởi hành. Nếu có nhiều lịch tối ưu, in ra bất kỳ lịch nào.

Ràng buộc

• $1\le k\le n\le 300000$
• $1\le c_i\le {10}^7$

Ví dụ