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

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ũ khi 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*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 <= n <= 20).

n dòng sau mỗi dòng chứa n số nguyên A[i,j] với A[i,j] là số tiền có được khi con gái thứ i kết hôn với tiến sỹ j (0

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ế.

Example

Input:
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output:
34 24
 
Note:  n<=16: time 1s, các trường hợp còn lại: time 2s.