Nợ báo cáo

Điểm: 1,36 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

by winterwolf94

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trở lại với năm 2013. Sau nhiều tuần rong ruổi trên khắp nước Mỹ, Trung trở về Atlanta tiếp tục học tại đại học X. Về đến nhà Trung mới biết trong đợt nghỉ đông vừa rồi, mỗi lớp học của Trung đều yêu cầu sinh viên viết báo cáo (lab report). Do mải mê đi chơi nên Trung chưa viết bài nào cả. Trung học ~N~ lớp, lớp thứ ~i~ yêu cầu ~M_i~ report. Nếu không nộp đủ số report của một môn trước deadline thì Trung sẽ phải học lại môn đó. Do không muốn học lại môn nào cả nên Trung chọn cách khác: đóng tiền phạt. Nếu Trung nộp một report trễ ~T~ giây và bài này có hệ số là ~A~ thì Trung sẽ đóng khoản tiền phạt là ~T~*~A~ cent.

Để cho việc viết dễ dàng hơn, Trung quyết định sẽ lần lượt viết tất cả các report của cùng một môn. Sau khi đã xong hết một môn Trung mới chuyển sang môn khác. Nếu môn ~i~ có ~M_i~ report, Trung có thể viết Mi report này theo bất kì thứ tự nào. Trung cũng có thể chọn thứ tự môn bất kì để viết report. Hiển nhiên Trung sẽ chọn thứ tự môn và report sao cho tổng số tiền đóng phạt là nhỏ nhất. Nếu có nhiều cách sắp xếp, Trung sẽ chọn cách để thứ tự từ điển của dãy các môn học theo trình tự viết nhỏ nhất. Nếu trong một môn có nhiều cách sắp xếp các report, Trung cũng sẽ chọn cách để dãy thứ tự các report trong môn đó theo trình tự viết nhỏ nhất.

Coi như tất cả các report có cùng deadline và ngay sau deadline Trung sẽ bắt tay vào viết report.

Input

Dòng đầu tiên gồm số nguyên dương ~N~ -- số môn học. ~N~ nhóm dòng tiếp theo, nhóm dòng thứ ~i~ có cấu trúc như sau:
- Dòng đầu là ~M_i~ -- số report của môn ~i~
- Dòng thứ 2 gồm ~M_i~ số nguyên dương ~T_{i,j}~ là thời gian (tính theo giây) Trung cần để viết bài report thứ ~j~ của môn ~i~
- Dòng thứ 3 gồm Mi số nguyên dương ~A_{i,j}~ là hệ số bài report thứ ~j~ của môn ~i~

Output

Dòng đầu tiên ghi số nguyên ~S~ -- tổng tiền phạt Trung phải đóng. ~N~ nhóm dòng tiếp theo, nhóm thứ ~i~ gồm 2 dòng có cấu trúc:
- Dòng đầu là ~K~-- số thứ tự của môn học thứ ~i~ mà Trung viết report
- Dòng thứ 2 gồm dãy số nguyên dương BK (gồm MK số) là số thứ tự các report của môn ~K~ theo trình tự được viết.

Giới hạn

~1 \leq N \leq~ ~10^5~ , ~1 \leq~ ~M_i~ ~\leq 2~*~10^5~
~1 \leq~ ~A_{i,j}~ , ~T_{i,j}~ ~\leq 5~*~10^5~
Tổng số report không quá ~3~*~10^5~.
Trong ~30\%~ số test, ~N = 1~.

Sample Input

Sample Output

Note

Gỉải thích: đầu tiên viết report của môn 2, nộp phạt ~4 \times 2~ ~+~ ~3\times (2 + 2)~ ~=~ ~20~ cent. Sau đó chuyển qua viết report của môn 1, nộp phạt tiếp ~2 \times~ ~(1 + 2 + 2)~ ~+ 1 \times~ ~(1 + 1 + 2 + 2)~ ~= 16~ cent. Tổng tiền nộp phạt ~20 + 16 = 36~ cent

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.