Đề bài

Chuyện kể rằng ngày xưa, bác Hoàng mới tốt nghiệp đại học và được chính phủ cử sang Việt Nam để kết giao và mở đường buôn bán.

Tuy nhiên, vừa sang đến biên giới thì giỏ lương thực của bác bị lũ khỉ núi chôm mất. May thay, gần đó có một bản làng người Tày đã nhiệt tình tiếp đón.

Trong buổi tiệc, bác Hoàng lỡ ba hoa về tấm bằng đại học vừa nhận. Để khoe mẽ, bác đưa ra một bài toán để đánh cược tấm bằng. Các bô lão trong làng bật cười và gọi một đứa bé 5 tuổi vào thử giải. Đứa bé trả lời:

Những bài toán này 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 Hoàng thấy thế mới cầu xin được gặp cô bé ấy để nghe lời giải, mong mang về lãnh thưởng từ viện Hàn lâm khoa học của nước mình.

Cô bé 4 tuổi vừa ở lớp mẫu giáo về, được mời đến gặp bác Hoàng. Nghe lời giải của cô, bác vô cùng sửng sốt. Câu chuyện đến tai một nhà báo trong vùng và được đăng ngay trong ngày. Bài toán như sau:

Bác Hoàng có N người con gái nuôi và muốn gả cho N vị tiến sĩ trẻ trong năm ấy.
Một nhà hiền triết sau khi xem xét đã lập ra một bảng N × N.

Ông giải thích:

• Nếu con gái thứ i kết hôn với tiến sĩ j thì bác Đào sẽ nhận được A_i,j tài sản suốt đời.

Vấn đề là làm sao sắp xếp các cuộc hôn nhân để tổng tài sản là lớn nhất.

Về sau, bài toán trở thành câu đố dân gian, đến mức mỗi em bé mẫu giáo người Tày đều giải được.
Hôm nay anh đưa bài này lên với một yêu cầu bổ sung:

• Hãy tìm số cách khác nhau để đạt cùng một tổng tài sản lớn nhất.

Input

• Dòng đầu tiên: số nguyên n (1 ≤ n ≤ 20).
• n dòng tiếp theo: mỗi dòng gồm n số nguyên A_i,j (0 ≤ A_i,j ≤ 10⁷), biểu thị tài sản nhận được nếu con gái thứ i kết hôn với tiến sĩ j.

Output

• In ra hai số nguyên:
  1. Tổng tài sản lớn nhất nhận được.
  2. Số cách ghép hôn nhân khác nhau để đạt được tổng tài sản đó.
  3.

sample input

4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Sample output

34 24