Để trang trí cho buổi lễ bế mạc của kỳ thi Olympic truyền thống 30 tháng 4, bạn Hạnh Giang dự định thiết kế một mạng lưới gồm các bóng đèn và dây đèn treo trên trần nhà. Mỗi dây đèn kết nối chính xác hai bóng đèn, và giữa mỗi cặp bóng đèn bất kỳ có không quá một dây đèn. Hiện tại, Hà đã chuẩn bị sẵn ~n~ bóng đèn màu với các màu sắc khác nhau, các bóng đèn này được đánh số từ ~1~ đến ~n~.

Sau khi tính toán các yếu tố về ánh sáng và màu sắc, Hạnh Giang muốn khoảng cách giữa bóng đèn màu thứ ~i~ và bóng đèn màu thứ ~j~ chính xác bằng ~a_{ij}~, với khoảng cách giữa hai bóng đèn là số lượng dây đèn ít nhất kết nối chúng. Hà có thể mua thêm một số bóng đèn trắng để hoàn thiện vào mạng lưới của mình, tuy nhiên do ngân sách cho buổi lễ này có hạn nên bạn phải tìm cách mua thêm ít bóng đèn trắng nhất có thể (tuy nhiên không có giới hạn về số lượng dây đèn được mua thêm). Bạn hãy giúp Hạnh Giang tìm ra một phương án hợp lệ sử dụng ít bóng đèn trắng nhất nhé.

Dữ liệu:

• Dòng đầu tiên gồm một số nguyên dương n là số bóng đèn màu ~(2≤n≤20)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên không âm ~a_{i1}, a_{i2}, …, a_{in}~ là khoảng cách giữa các cặp bóng đèn màu ~(a_{ii}=0, 1≤a_{ij}=a_{ji}≤10 ∀i≠j)~.

Kết quả:

• Nếu không tồn tại phương án thỏa mãn, in ra hai số ~-1~ trên một dòng.
• Ngược lại, in ra kết quả theo định dạng sau:
• Dòng đầu tiên gồm hai số nguyên dương ~k,m~ lần lượt là số lượng bóng đèn trắng và dây đèn mà Hạnh Giang phải mua thêm.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~i,j~ mô tả một dây đèn kết nối bóng đèn thứ ~i~ và bóng đèn thứ ~j~ ~(1 ≤ i < j ≤ n+k)~. Các bóng đèn trắng mà Hạnh Giang mua thêm được đánh số từ ~n+1~ đến ~n+k~.

Chấm điểm

Gọi ~k_p~ là số bóng đèn trắng cần thêm vào trong phương án của bạn, ~k_j~ là số bóng đèn trắng cần thêm vào trong phương án của giám khảo. Nếu điểm tối đa của test là ~1~, điểm của bạn được tính như sau:

• Nếu ~k_p \le k_j~, bạn được ~1~ điểm cho test đó.
• Nếu ~k_p > k_j + 400~, bạn được ~0~ điểm cho test đó.
• Nếu ~k_j < k_p \le k_j + 400~, điểm của bạn (~S~) sẽ được tính theo công thức:

~S = 1 - (\frac{k_p - k_j - 0.75}{400})^{0.25}~

Nộp bài

Các bạn có thể nộp bài bằng một trong hai cách sau:

• Nộp code: Bạn có thể nộp code như một bài bình thường, nhập dữ liệu từ stdin, in kết quả ra stdout, giới hạn thời gian để đoạn code của bạn đưa ra kết quả là ~40~ giây.
• Nộp bài theo từng test: Sử dụng ngôn ngữ TEXT. Sao chép output của bạn cho một test vào khung code. Tuy nhiên cách nộp bài này chỉ nộp được 1 test một lần.

Testcase

Bộ test bài gồm ~6~ testcase, mỗi testcase có giá trị ~1~ điểm.

Test 1 ~(k_j = 15)~

5
0 10 7 7 8
10 0 7 9 6
7 7 0 6 4
7 9 6 0 5
8 6 4 5 0

Test 2 ~(k_j = 43)~

10
0 3 8 7 6 7 7 6 9 6
3 0 7 6 6 5 7 7 9 6
8 7 0 7 6 6 7 7 3 8
7 6 7 0 10 6 7 9 8 5
6 6 6 10 0 8 9 4 5 8
7 5 6 6 8 0 5 5 5 3
7 7 7 7 9 5 0 7 6 7
6 7 7 9 4 5 7 0 7 5
9 9 3 8 5 5 6 7 0 6
6 6 8 5 8 3 7 5 6 0

Test 3 ~(k_j = 32)~

10
0 8 5 4 7 8 8 6 5 7
8 0 9 10 6 9 5 6 7 4
5 9 0 6 6 3 8 5 2 5
4 10 6 0 8 8 9 6 7 8
7 6 6 8 0 3 6 3 4 4
8 9 3 8 3 0 8 5 4 6
8 5 8 9 6 8 0 4 6 5
6 6 5 6 3 5 4 0 3 4
5 7 2 7 4 4 6 3 0 3
7 4 5 8 4 6 5 4 3 0

Test 4 ~(k_j = 69)~

20
0 3 2 8 6 8 4 8 4 5 4 5 3 5 6 8 4 4 7 6
3 0 4 7 4 6 4 7 3 5 4 4 4 4 4 6 5 3 5 4
2 4 0 7 5 7 4 7 4 4 3 4 4 5 5 8 4 4 7 5
8 7 7 0 9 9 8 6 8 8 9 8 8 6 6 5 9 7 8 7
6 4 5 9 0 8 7 9 5 2 7 6 6 6 6 8 8 5 7 7
8 6 7 9 8 0 5 7 7 8 7 5 7 7 7 8 8 5 7 3
4 4 4 8 7 5 0 5 5 6 3 5 6 6 7 6 6 5 6 5
8 7 7 6 9 7 5 0 7 8 7 6 8 5 6 2 9 5 3 5
4 3 4 8 5 7 5 7 0 4 5 4 4 4 5 7 6 3 6 6
5 5 4 8 2 8 6 8 4 0 6 5 5 7 6 8 7 4 8 6
4 4 3 9 7 7 3 7 5 6 0 4 4 6 7 8 6 5 6 5
5 4 4 8 6 5 5 6 4 5 4 0 4 5 6 7 4 4 6 4
3 4 4 8 6 7 6 8 4 5 4 4 0 5 6 8 5 4 6 5
5 4 5 6 6 7 6 5 4 7 6 5 5 0 6 6 6 4 5 6
6 4 5 6 6 7 7 6 5 6 7 6 6 6 0 5 8 3 5 5
8 6 8 5 8 8 6 2 7 8 8 7 8 6 5 0 10 6 4 6
4 5 4 9 8 8 6 9 6 7 6 4 5 6 8 10 0 6 8 6
4 3 4 7 5 5 5 5 3 4 5 4 4 4 3 6 6 0 5 5
7 5 7 8 7 7 6 3 6 8 6 6 6 5 5 4 8 5 0 5
6 4 5 7 7 3 5 5 6 6 5 4 5 6 5 6 6 5 5 0

Test 5 ~(k_j = 51)~

20
0 7 5 5 7 4 6 7 5 5 7 3 5 3 5 3 6 5 5 5
7 0 10 7 6 7 9 9 3 8 7 5 10 9 7 9 9 10 9 7
5 10 0 6 5 8 9 7 8 3 5 7 7 4 7 3 8 5 5 5
5 7 6 0 5 5 7 4 5 4 4 3 6 7 5 6 5 6 4 2
7 6 5 5 0 7 6 4 4 3 2 5 6 6 3 5 5 5 5 4
4 7 8 5 7 0 3 5 5 7 7 3 5 6 5 6 6 8 7 5
6 9 9 7 6 3 0 7 7 7 7 5 3 8 4 8 4 7 9 7
7 9 7 4 4 5 7 0 7 5 3 5 7 8 6 7 6 7 5 3
5 3 8 5 4 5 7 7 0 6 5 3 8 7 5 7 7 8 7 5
5 8 3 4 3 7 7 5 6 0 3 5 5 4 5 3 6 3 5 3
7 7 5 4 2 7 7 3 5 3 0 5 7 6 4 5 6 5 4 3
3 5 7 3 5 3 5 5 3 5 5 0 6 5 3 5 5 7 5 3
5 10 7 6 6 5 3 7 8 5 7 6 0 7 4 7 2 5 7 5
3 9 4 7 6 6 8 8 7 4 6 5 7 0 7 2 8 6 4 6
5 7 7 5 3 5 4 6 5 5 4 3 4 7 0 7 3 7 7 5
3 9 3 6 5 6 8 7 7 3 5 5 7 2 7 0 8 5 3 5
6 9 8 5 5 6 4 6 7 6 6 5 2 8 3 8 0 6 6 4
5 10 5 6 5 8 7 7 8 3 5 7 5 6 7 5 6 0 7 5
5 9 5 4 5 7 9 5 7 5 4 5 7 4 7 3 6 7 0 3
5 7 5 2 4 5 7 3 5 3 3 3 5 6 5 5 4 5 3 0

Test 6 ~(k_j = 86)~

20
0 7 3 7 5 1 4 5 6 5 5 5 7 1 6 5 6 5 5 4
7 0 7 6 5 8 10 7 3 6 6 10 8 8 7 8 8 6 5 4
3 7 0 4 3 2 4 4 6 4 7 6 7 4 7 8 3 6 6 4
7 6 4 0 2 6 8 4 5 4 5 8 6 8 8 6 6 4 5 6
5 5 3 2 0 4 6 2 7 5 6 8 5 6 9 8 4 4 5 6
1 8 2 6 4 0 3 4 6 4 6 4 8 2 7 6 5 6 6 4
4 10 4 8 6 3 0 6 8 6 9 6 10 4 9 7 7 9 9 6
5 7 4 4 2 4 6 0 9 6 8 8 6 6 10 9 3 6 6 7
6 3 6 5 7 6 8 9 0 4 5 9 7 7 5 10 7 4 5 6
5 6 4 4 5 4 6 6 4 0 5 8 8 6 7 9 7 4 3 4
5 6 7 5 6 6 9 8 5 5 0 8 6 6 5 9 6 4 5 3
5 10 6 8 8 4 6 8 9 8 8 0 5 4 9 4 9 8 8 6
7 8 7 6 5 8 10 6 7 8 6 5 0 8 7 7 7 4 6 5
1 8 4 8 6 2 4 6 7 6 6 4 8 0 7 6 7 6 6 4
6 7 7 8 9 7 9 10 5 7 5 9 7 7 0 10 7 6 6 3
5 8 8 6 8 6 7 9 10 9 9 4 7 6 10 0 9 7 9 8
6 8 3 6 4 5 7 3 7 7 6 9 7 7 7 9 0 6 6 4
5 6 6 4 4 6 9 6 4 4 4 8 4 6 6 7 6 0 4 3
5 5 6 5 5 6 9 6 5 3 5 8 6 6 6 9 6 4 0 3
4 4 4 6 6 4 6 7 6 4 3 6 5 4 3 8 4 3 3 0