marukaite

太郎君は小学生で、チラシの裏に落書きをしています。 ある時、太郎君は次のゲームを思いつきました。

• n×nの格子状のマス目を書いておきます。
• それぞれのマス目の初期状態は、丸印が書かれているか、書かれていないかのどちらか一方です。
• これらの丸印を消したり書いたりして最終的にどの一列を見ても必ずちょうど1つのみの丸印が、どの一行を見ても必ず1つのみの丸印が存在するようにすることが目標であり、この状態にすればゲームをクリアしたことになります。

太郎君はこのゲームを思いつきましたが、太郎君はこのゲームをクリアするのに大変時間がかかってしまいます。そこで、大学生であるあなたに助けを求めました。 太郎君の兄であり大学生であるあなたの仕事は以下の通りです。 厳密な状況を考えるために、あるマス目に丸印を書き込むコスト、あるマス目にある丸印を消すコストをあなたは導き出しました。このコストを用いてこのゲームをクリアするためにかかる操作のコストを最小化するような手順を考える。 このとき、最小のコストおよびそのコストを達成するような手順を出力するプログラムを書いてください。 出力については、最小コストを達成する手順なら、どのような操作、順番でも出力してもよいものとする。

n
W11 W12 .. W1n
W21 W22 .. W2n
..
Wn1 Wn2 .. Wnn
E11 E12 .. E1n
E21 E22 .. E2n
..
En1 En2 .. Enn
F1(n文字)
F2(n文字)
..
Fn(n文字)

• nは太郎君の作ったマス目が一辺にいくつあるかを表す

• Wijは上からi番目、左からj番目のマス目に丸印を書き込むコストを表す

• Eijは上からi番目、左からj番目のマス目に書かれてある丸印を消すコストを表す

• Fiは上からi番目の行のマス目の初期状態を表す

• Fiの左からj文字目について

  • 'o'のとき、上からi番目、左からj番目のマス目に丸印が書かれてあることを表す。
  • '.'のとき、上からi番目、左からj番目のマス目が空白であることを表す。

mincost
cnt
R1 C1 operate1
R2 C2 operate2
..
Rcnt Ccnt operatecnt

• mincostは、太郎君のゲームをクリアするために必要な最小コストを表す。

• mincostは書き込み操作、消去操作で発生するコストの総和で計算される。

• cnt : mincostのコストを達成する操作を行った回数を表す

• k回目(1≤k≤cnt)に実行する操作はk+2行目に記述する

• k回目(1≤k≤cnt)の操作に対して

  • 上からi番目のマス目、左からj番目のマス目に対して行ったものとすると
  • Rkkである。
  • この操作が丸印を消す操作であるならばoperatek = "erase"とせよ
  • この操作が丸印を書き込む操作であるならばoperatek = "write"とせよ
  • Rk,Ck,operatekは一行に空白区切りで出力しなければならない

• 丸印の書かれてあるマス目に対して丸印を記述する操作、および丸印が書かれていないマス目に対して丸印を消去する操作をした場合はWrongAnswerである

• cnt個の操作にかかるコストの総和がmincostに一致しないときはWrongAnswerである

• 1≤ n ≤ 100
• 1≤ Wij ≤ 1000
• 1≤ Eij ≤ 1000
• Fiは文字列であり、その長さはnである
• Fiは'o'と'.'のみで構成されている