The problem for kid

View as PDF

Submit solution


Points: 0.49 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Trần Mạnh Chánh Quân
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Chuyện kể rằng ngày xưa, bác HCĐào mới tốt nghiệp đại học, được chính phủ nước Trái Na cho sang Việt Nam để xin được kết giao, lưu thông buôn bán. Tuy nhiên, vừa sang được biên giới, thì giỏ lương thực của bác đã bị lũ khỉ núi chôm mất. Thật may cho bác là cách đó không xa là bản làng của người Tày, và họ đã tiếp đón nhiệt tình. Trong buổi tiệc tiếp đón ở vùng núi, bác lỡ ba hoa về tấm bằng đại học mới nhận được. Cũng muốn khoe mẽ nên bác ấy đề ra một bài toán cho các bô lão, và dùng tấm bằng để đánh cược. Các bô lão bật cười, và gọi một đứa bé ~5~ tuổi đang chơi ngoài sân vào chơi thử. Thế rồi đứa bé đó trả lời rằng: "Những bài toán này thì con mới thua đố cược em gái con ngày hôm qua xong. Chẳng đáng để con phải làm."

Bác Đào thấy thế mới cầu xin được gặp con bé để nghe lời giải, để mang về lãnh thưởng viện Hàn lâm khoa học Trái Na.

Cô bé ~4~ tuổi vừa ở lớp mẫu giáo về, được mời vào gặp bác Đào, bác ấy vô cùng sửng sốt trước câu trả lời này. Câu chuyện này đến tai một nhà báo nghiệp dư trong vùng. Và được đăng lên số báo ngày hôm đó. Bài toán đó như sau:

Bác Đào có ~N~ người con gái nuôi, và muốn gả cho ~N~ vị tiến sỹ trẻ năm ấy. Thế nhưng không biết nên sắp xếp hôn nhân thế nào cho lợi. Một nhà hiền triết được mời đến để tham khảo ý kiến. Nhà hiền triết sau khi xem xét đã báo cáo kết quả thành ~1~ bảng ~N \times N~ và nói rằng "nếu cô con gái thứ ~i~ kết hôn cùng tiến sỹ ~j~ thì sẽ làm ra được lượng tài sản bằng với số ở hàng ~i~ cột ~j~ từ nay đến hết đời". Nhưng khổ nỗi ông hiền triết cũng không biết sắp xếp hôn nhân sao cho bác Đào có được ngôi mộ hoành tráng nhất sau khi bác chết.

Về sau, bài toán trở thành câu đố dân gian của người Tày và mỗi em bé mẫu giáo nơi đây đều giải được...

Để thư giãn xã hơi sau kì thi VM vừa qua, anh quandum ngỏ ý set bài này lên để mọi người thư giãn, đồng thời thêm ~1~ yêu cầu là có bao nhiêu cách để cho ra cùng ~1~ kết quả tốt nhất.

Input

Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 20)~.

~N~ dòng sau mỗi dòng chứa ~N~ số nguyên ~A_{ij}~ với ~A_{ij}~ là số tiền có được khi con gái thứ ~i~ kết hôn với tiến sĩ ~j~ ~(0 \le A_{ij} \le 10^7)~.

Output

Tổng tài sản lớn nhất nhận được và số cách để có được tổng tài sản như thế.

Sample Input

4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Sample Output

34 24

Comments

Please read the guidelines before commenting.


There are no comments at the moment.