Khuyến mãi ghế đẩu

Một siêu thị có $n$ mặt hàng, mỗi mặt hàng là một chiếc ghế đẩu (loại $1$) hoặc một chiếc bút chì (loại $2$). Mặt hàng thứ $i$ có giá $c_i$.

Siêu thị đang có chương trình khuyến mãi: nếu trong một giỏ hàng có ít nhất một chiếc ghế đẩu, thì mặt hàng rẻ nhất trong giỏ đó được giảm giá $50\%$ (giá của nó còn lại một nửa). Nếu có nhiều mặt hàng cùng có giá nhỏ nhất, chỉ một trong số chúng được giảm.

Bạn có $k$ giỏ hàng và muốn mua toàn bộ $n$ mặt hàng. Hãy phân phối tất cả mặt hàng vào các giỏ sao cho tổng số tiền phải trả (sau khi đã trừ khuyến mãi) là nhỏ nhất.

Lưu ý: phải dùng đúng cả $k$ giỏ, không giỏ nào được để trống. Mỗi giỏ có thể chứa số lượng ghế đẩu và bút chì tùy ý.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ — số mặt hàng và số giỏ.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $c_i$ và $t_i$ — giá và loại của mặt hàng thứ $i$ ($t_i=1$: ghế đẩu, $t_i=2$: bút chì).

Dữ liệu ra

• Dòng đầu in một số thực với đúng một chữ số sau dấu chấm — tổng số tiền nhỏ nhất sau khuyến mãi.
• $k$ dòng tiếp theo, mỗi dòng mô tả một giỏ theo dạng $t{b}_1{b}_2\dots b_t$, trong đó $t$ là số mặt hàng trong giỏ và $b_1,\dots ,b_t$ là chỉ số của các mặt hàng được xếp vào giỏ đó. Các mặt hàng được đánh số từ $1$ đến $n$ theo thứ tự nhập vào.

Mỗi mặt hàng phải thuộc đúng một giỏ. Có thể in các giỏ và các mặt hàng trong mỗi giỏ theo thứ tự bất kỳ. Nếu có nhiều cách phân phối tối ưu, in ra một cách bất kỳ.

Ràng buộc

• $1\le k\le n\le {10}^3$
• $1\le c_i\le {10}^9$
• $t_i\in \{1,2\}$

Ví dụ