Joitter là một mạng xã hội đang rất được quan tâm, giúp mọi người giao tiếp với người quen trên Internet thuận tiện hơn thông qua việc dễ dàng đăng những bài nhật ký ngắn và chia sẻ ảnh.

Trên Joitter, một người dùng có thể thêm những người dùng khác vào danh sách “bạn bè”. Khi người dùng \(A\) muốn thêm người dùng \(B\) làm bạn, \(B\) sẽ nhận được thông báo. Nếu \(B\) đồng ý, hai người được thêm vào danh sách bạn bè của nhau. Việc này được tính là một lần kết bạn. Vì một lý do nào đó, mỗi lần kết bạn có một chi phí phụ thuộc vào hai người dùng. Việc \(A\) và \(B\) là bạn, đồng thời \(B\) và \(C\) là bạn, không nhất thiết có nghĩa là \(A\) và \(C\) là bạn.

Mỗi người dùng có thể chọn một trong ba chế độ công khai nhật ký sau:

1. Chỉ cho phép bạn bè đọc.
2. Chỉ cho phép bạn bè hoặc bạn của bạn bè đọc.
3. Chỉ cho phép những người dùng có thể đi đến được bằng cách lần theo các quan hệ bạn bè đọc.

Có \(N\) người vừa đăng ký Joitter, mỗi người chọn một trong ba chế độ trên. Tình cờ, không có chế độ nào được đúng một người chọn: với mỗi người dùng, luôn có ít nhất một người khác chọn cùng chế độ với họ.

Yêu cầu

Ban đầu, chưa có quan hệ bạn bè nào giữa \(N\) người này. Hãy tìm số lần kết bạn ít nhất để mỗi người trong số họ đều đọc được nhật ký của tất cả những người còn lại. Trong các cách thực hiện dùng đúng số lần kết bạn ít nhất đó, hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số người dùng. Các người dùng được đánh số từ \(1\) đến \(N\).
• \(N\) dòng tiếp theo mô tả chế độ công khai nhật ký của từng người. Dòng thứ \(1+i\) (\(1\le i\le N\)) chứa một số nguyên \(1\), \(2\) hoặc \(3\), tương ứng với chế độ (1), (2) hoặc (3) của người dùng \(i\). Bảo đảm mỗi người dùng có ít nhất một người khác chọn cùng chế độ.
• \(N\) dòng tiếp theo mô tả chi phí kết bạn. Dòng thứ \(1+N+i\) (\(1\le i\le N\)) chứa \(N\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\) (\(1\le j\le N\)), ký hiệu \(C_{ij}\), là chi phí để người dùng \(i\) và \(j\) kết bạn. Với mọi \(i,j\), ta có \(C_{ii}=0\) và \(C_{ij}=C_{ji}\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa hai số nguyên cách nhau bởi dấu cách: số lần kết bạn nhỏ nhất để mọi người đều đọc được nhật ký của tất cả những người còn lại, và tổng chi phí nhỏ nhất để đạt được điều đó với đúng số lần kết bạn ấy.

Ràng buộc

• \(2\le N\le1000\).
• \(1\le C_{ij}\le1000\) với \(i\ne j\).
• \(C_{ii}=0\) và \(C_{ij}=C_{ji}\) với mọi \(1\le i,j\le N\).
• Giới hạn thời gian CPU: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

• Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm.

Ví dụ

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

15 62

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

4 20

3
3
3
3
0 8 7
8 0 9
7 9 0

2 15