조이터 (Joitter)

시간 제한1초메모리 제한1024 MB

요약

각 사용자의 일기 공개 범위와 사용자 쌍마다의 친구 등록 비용이 주어질 때, 모든 사람이 서로의 일기를 읽을 수 있게 하는 최소 친구 등록 수와 그 수를 달성하는 최소 비용을 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 그리디, 최소 신장 트리, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

조이터(Joitter)는 짧은 일기 글을 가볍게 올리고 사진을 공유하면서 지인과의 인터넷 소통을 더 편하게 만들어 주는, 요즘 화제인 소셜 네트워킹 서비스(SNS)이다.

조이터에서는 자기 자신이 아닌 다른 사용자를 "친구"라는 목록에 등록할 수 있다. 어떤 사용자 A가 어떤 사용자 B를 "친구"로 등록하려 하면 사용자 B에게 알림이 간다. 사용자 B가 이를 허락하면 두 사람은 서로를 "친구"로 등록하게 된다. 이것을 한 번의 "친구" 등록이라 한다. "친구" 등록에는 어째서인지 두 사용자에 따라 달라지는 비용이 든다. 사용자 A와 사용자 B가 서로 "친구"이고 사용자 B와 사용자 C가 서로 "친구"이더라도, 사용자 A와 사용자 C가 서로 "친구"가 된다고는 할 수 없다.

조이터에서 사용자는 일기의 공개 설정을 다음 세 가지 중 하나로 정할 수 있다.

"친구"에게만 공개한다.
"친구" 또는 "친구"의 "친구"인 사용자에게만 공개한다.
"친구" 관계를 따라가 도달할 수 있는 사용자에게만 공개한다.

N명이 새로 조이터에 가입했다. 일기의 공개 설정으로 각자는 위의 (1), (2), (3) 중 하나를 골랐다. 우연히도, N명 중 정확히 한 명만이 고른 공개 설정은 존재하지 않았다.

현재 N명 사이에는 "친구" 관계가 전혀 등록되어 있지 않다. N명 모두가 다른 모두의 일기를 읽을 수 있게 하려면 최소 몇 번의 "친구" 등록이 필요할까? 또, 최소 횟수의 "친구" 등록으로 이를 달성하기 위한 최소 비용은 얼마일까?

N명의 일기 공개 설정과 각 두 사람의 쌍이 "친구"로 등록되는 데 드는 비용이 주어질 때, N명 모두가 다른 모두의 일기를 읽을 수 있게 하기 위한 "친구" 등록 횟수의 최솟값과, 그 횟수를 실현하는 최소 비용을 구하는 프로그램을 작성하시오.

입력

표준 입력에서 다음 입력을 읽는다.

1번째 줄에는 정수 N이 적혀 있으며, 사용자의 수를 나타낸다. 사용자에게는 1부터 N까지의 번호가 붙어 있다.
이어지는 N개 줄에는 각 사용자의 일기 공개 설정이 적혀 있다. 1 + i번째 줄 (1 ≤ i ≤ N)에는 사용자 i의 일기 공개 설정을 나타내는 정수 하나가 적혀 있다. 이 정수는 1, 2, 3 중 하나이며, 공개 설정 (1), (2), (3)에 각각 대응한다. 어떤 사용자에 대해서도 다른 누군가와 같은 공개 설정인 것이 보장된다.
이어지는 N개 줄에는 "친구" 등록을 위한 비용이 적혀 있다. 1 + N + i번째 줄 (1 ≤ i ≤ N)에는 N개의 정수가 공백으로 구분되어 적혀 있으며, 그중 j번째 (1 ≤ j ≤ N) 정수 Cij는 사용자 i와 사용자 j가 친구로 등록되는 데 드는 비용을 나타낸다. 임의의 i, j에 대해 Cii = 0 및 Cij = Cji를 만족한다.

출력

표준 출력에, N명 모두가 모두의 일기를 읽을 수 있게 하기 위한 "친구" 등록 횟수의 최솟값과 그 횟수를 실현하는 최소 비용을 나타내는 두 정수를 공백으로 구분하여 한 줄에 출력하라.

제한

2 ≤ N ≤ 1 000 (사용자의 수)
1 ≤ Cij ≤ 1 000 ((i, j) "친구" 등록을 위한 비용)

예제3

예제 1

입력

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

예제 2

입력

예상 출력

4 20

예제 3
입력
```
3
3
3
3
0 8 7
8 0 9
7 9 0
```
예상 출력
```
2 15
```