Giải bài trực tuyến

            Trở lại với năm 2013. Sau nhiều tuần rong ruổi trên khắp nước Mỹ, Trung trở về Atlanta tiếp tục học tại đại học X. Về đến nhà Trung mới biết trong đợt nghỉ đông vừa rồi, mỗi lớp học của Trung đều yêu cầu sinh viên viết báo cáo (lab report). Do mải mê đi chơi nên Trung chưa viết bài nào cả. Trung học N lớp, lớp thứ i yêu cầu M_i report. Nếu không nộp đủ số report của một môn trước deadline thì Trung sẽ phải học lại môn đó. Do không muốn học lại môn nào cả nên Trung chọn cách khác : đóng tiền phạt. Nếu Trung nộp một report trễ T giây và bài này có hệ số là A thì Trung sẽ đóng khoản tiền phạt là T x A cent.

         Để cho việc viết dễ dàng hơn, Trung quyết định sẽ lần lượt viết tất cả các report của cùng một môn. Sau khi đã xong hết một môn Trung mới chuyển sang môn khác. Nếu môn i có M_i report, Trung có thể viết M_i report này theo bất kì thứ tự nào. Trung cũng có thể chọn thứ tự môn bất kì để viết report. Hiển nhiên Trung sẽ chọn thứ tự môn và report sao cho tổng số tiền đóng phạt là nhỏ nhất. Nếu có nhiều cách sắp xếp, Trung sẽ chọn cách để thứ tự từ điển của dãy các môn học theo trình tự viết nhỏ nhất. Nếu trong một môn có nhiều cách sắp xếp các report, Trung cũng sẽ chọn cách để dãy thứ tự các report trong môn đó theo trình tự viết nhỏ nhất.

         Coi như tất cả các report có cùng deadline và ngay sau deadline Trung sẽ bắt tay vào viết report.

Input

            Dòng đầu tiên gồm số nguyên dương N – số môn học.
         N nhóm dòng tiếp theo, nhóm dòng thứ i có cấu trúc như sau :

• dòng đầu là M_i – số report của môn i
• dòng thứ 2 gồm M_i số nguyên dương T_i,j là thời gian (tính theo giây) Trung cần để viết bài report thứ j của môn i
• dòng thứ 3 gồm M_i số nguyên dương A_i,j là hệ số bài report thứ j của môn i

Giới hạn :             1 <= N <= 10⁵,                    1 <= M_i <= 2 x 10⁵
                          1 <= A_i,j , T_i,j <= 5 x 10⁵ 
                          Tổng số report không quá 3 x 10⁵.
                          Trong 30% số test, N = 1.

Output

                Dòng đầu tiên ghi số nguyên S – tổng tiền phạt Trung phải đóng.
            N nhóm dòng tiếp theo, nhóm thứ i gồm 2 dòng có cấu trúc :

• dòng đầu là K– số thứ tự của môn học thứ i mà Trung viết report
• dòng thứ 2 gồm dãy số nguyên dương B_K (gồm M_K số) là số thứ tự các report của môn K theo trình tự được viết.

Example

Input:
2
2
1 1
1 2
2
2 2

3 4
Output:
36
2
2 1
1
2 1

Gỉải thích : đầu tiên viết report của môn 2, nộp phạt 4x2 + 3x(2+2) = 20cent.

Sau đó chuyển qua viết report của môn 1, nộp phạt tiếp 2 * (1+2+2) + 1 * (1+1+2+2) = 16 cent. 

Tổng tiền nộp phạt 20+16=36 cent