24095번 - ジョイッター (Joitter) 다국어

ジョイッター (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 人全員が他の全員の日記を読めるようになるための「友人」登録の回数の最小値と，その回数を実現する 最小のコストを求めるプログラムを作成せよ．

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

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

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

• 2 ≤ N ≤ 1 000 ユーザの人数
• 1 ≤ C_ij ≤ 1 000 (i , j) 「友人」登録のためのコスト