joitter(ジョイッター) - joi2011-day1

時間制限: 1秒

メモリ制限: 64MB

ジョイッター (Joitter) は，短い日記の気軽な投稿や写真の共有を通して，知り合いとのインターネット上でのコミュニケーションをより快適にする，話題沸騰中のソーシャル・ネットワーキング・サービス (SNS) である．

ジョイッターでは，自分以外のユーザを「友人」というリストに登録することができる．あるユーザ A があるユーザ B を「友人」として登録しようとすると，ユーザ B に通知が届く．ユーザ B がこれに許可することで，2 人は互いに「友人」として登録される．これを 1 回の「友人」登録と考える．「友人」登録には，なぜか 2 人のユーザに依存したコストがかかる．ユーザ A とユーザ B が互いに「友人」でありユーザ B とユーザ C が互いに「友人」であっても，ユーザ A とユーザ C が互いに「友人」となるとは限らない．

ジョイッターでは，ユーザは日記の公開設定を以下の 3 種類のいずれかに設定できる．

(1) 「友人」にのみ公開する．
(2) 「友人」あるいは「友人」の「友人」であるユーザにのみ公開する．
(3) 「友人」関係を辿って到達できるユーザにのみ公開する．

N 人が新しくジョイッターに登録した．日記の公開設定として各々が上記の (1), (2), (3) のいずれかを選んだ．偶然にも，N 人の中でちょうど 1 人だけが選んだ公開設定は存在しなかった．

現在，N 人の間の「友人」関係は全く登録されていない．N 人全員が他の全員の日記を読めるようになるには，最小で何回の「友人」登録が必要であろうか．また，最小回数の「友人」登録でこれを達成するための最小のコストはいくらになるだろうか．

課題

N 人の日記の公開設定と，各 2 人の組が「友人」として登録されるためのコストが与えられたとき，N 人全員が他の全員の日記を読めるようになるための「友人」登録の回数の最小値と，その回数を実現する最小のコストを求めるプログラムを作成せよ．

制限

`2 \leq N \leq 1\,000`	ユーザの人数
`1 \leq C_{i j} \leq 1\,000 (i \neq j)`	「友人」登録のためのコスト

入力

標準入力から以下の入力を読み込め．

1 行目には整数 N が書かれており，ユーザの人数を表す．ユーザには 1 から N までの番号がつけられている．
続く N 行には各ユーザの日記の公開設定が書かれている．1 + i 行目 (1 \leq i \leq N) には，ユーザ i の日記の公開設定を表す 1 つの整数が書かれている．この整数は 1, 2, 3 のいずれかであり，公開設定 (1), (2), (3) のそれぞれに対応する．どのユーザに対しても，他の誰かとは同じ公開設定になっていることが保証されている．
続く N 行には「友人」登録のためのコストが書かれている．1 + N + i 行目 (1 \leq i \leq N) には N 個の整数が空白を区切りとして書かれており，そのうちの j 番目 (1 \leq j \leq N) の整数 C_{i j} は，ユーザ i とユーザ j が友人として登録されるためのコストを表す．任意の i, j に対して C_{i i} = 0 および C_{i j} = C_{j i} を満たす．

出力

標準出力に，N 人全員が全員の日記を読めるようになるための「友人」登録の回数の最小値と，その回数を実現する最小のコストを表す 2 つの整数を，空白を区切りとして 1 行に出力せよ．

入出力の例

入力例1	出力例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	出力例2
`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 3 3 0 8 7 8 0 9 7 9 0`	`2 15`