JOI Flag(日本情報オリンピック旗) - joi2012-day1

出典: 第11回日本情報オリンピック 日本代表選手選考会

時間制限: 1.5秒

メモリ制限: 64MB

あなたは，日本情報オリンピックの新しい旗として，レベル K の JOI Flag を作ることにした．

ただし，

例えば，



OIJJ

JJJJ

OOII

OOII

は，レベル 2 の JOI Flag である．また，



IIIIIIOO

IIIIIIOO

IIIIJOJJ

IIIIOIJJ

JJJJOOOO

JJJJOOOO

JJJJOOOO

JJJJOOOO

は，レベル 3 の JOI Flag である．

あなたの手元には，いくつかのマス目に J, O, I のいずれかの文字が書きこまれた 2^K \times 2^K の旗がある．

あなたは，この旗にいくつかの文字を書き加えたり，既に旗に書かれているいくつかの文字を修正したりして，レベル K の JOI Flag を完成させることにした．文字が書かれていないマスにはコスト 0 で文字を書けるが，文字が書かれたマスの文字を書き換えるにはコスト 1 がかかる．

レベル K の JOI Flag を完成させるのに必要なコストの最小値を求めたい．

課題

あなたの手元にある旗の情報が与えられたとき，レベル K の JOI Flag を完成させるのに必要なコストの最小値を求めるプログラムを作成せよ．

制限

1 \leqq K \leqq 30 JOI Flag のレベル
1 \leqq N \leqq 1\,000 JOI Flag に書き込まれている文字の個数
1 \leqq X_i \leqq 2^K i 番目の文字の書かれている列番号
1 \leqq Y_i \leqq 2^K i 番目の文字の書かれている行番号
C_i は J, O, I のいずれかである．
組 (X_i, Y_i) はすべて異なる．

入力

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

出力

標準出力に，レベル K の JOI Flag を作るのに必要なコストの最小値を表す整数を 1 行で出力せよ．

採点基準

採点用データのうち，配点の 40% 分については，K \leqq 10 を満たす．

入出力の例

入力例1 出力例1
2 10
2 2 J
3 3 I
1 3 I
1 1 O
3 2 J
2 1 I
4 1 O
3 4 I
4 4 O
2 3 O		 3

この入力は，



OI-O

-JJ-

IOI-

--IO

という旗を表す．ただし，何も書かれていないマス目を – で表すとする。

これはコスト 3 で



OIJJ

JJJJ

OOII

OOII

にすることができる．

入力例2 出力例2
4 30
16 14 J
2 8 O
10 9 J
10 13 I
6 6 O
11 14 I
1 2 I
3 2 O
3 10 O
1 12 I
4 11 I
9 5 J
15 1 O
12 4 I
16 5 J
10 7 J
3 8 J
4 10 I
4 7 I
2 11 I
2 12 O
15 5 J
15 7 J
6 9 J
5 7 O
14 5 J
12 11 J
15 10 O
13 16 I
13 11 I		 9