시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 1 1 50.000%

문제

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

  • レベル 0 の JOI Flag とは,1 × 1 のマス目からなる旗で,J, O, I のいずれかの文字が書かれたもので ある.
  • 整数 m > 0 に対し,レベル m の JOI Flag とは,2m × 2m のマス目からなる旗で,各マスに J, O, I の いずれかの文字が書かれたもののうち,次の条件を満たすものである:マス目全体を 2m−1 × 2m−1 の 正方形 4 つに分けたとき,レベル m − 1 の JOI Flag ,J の書かれたマスのみからなる部分,O の書 かれたマスのみからなる部分,I の書かれたマスのみからなる部分の 4 つの部分に分かれる.

例えば,

OIJJ
JJJJ
OOII
OOII

は,レベル 2 の JOI Flag である.また,

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

は,レベル 3 の JOI Flag である.

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

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

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

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

입력

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

  • 1 行目には整数 K, N が空白を区切りとして書かれている.K は JOI Flag のレベルを,N は文字の書 かれたマス目の個数をそれぞれ表す.文字には 1, 2, ··· , N の番号がつけられている.
  • 続く N 行には文字の情報が書かれている.i + 1 行目には Xi, Yi,Ci が空白を区切りとして書かれてい る.これは,文字 Ci が左から Xi 列目,上から Yi 行目に書かれていることを表す.

출력

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

제한

  • 1 ≤ K ≤ 30 JOI Flag のレベル
  • 1 ≤ N ≤ 1 000 JOI Flag に書き込まれている文字の個数
  • 1 ≤ Xi ≤ 2K i 番目の文字の書かれている列番号
  • 1 ≤ Yi ≤ 2K i 番目の文字の書かれている行番号
  • Ci は J, O, I のいずれかである.
  • 組 (Xi, Yi) はすべて異なる.

예제 입력 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

예제 출력 1

3

この入力は,

OI-O
-JJ-
IOI-
--IO

という旗を表す.ただし,何も書かれていないマス目を - で表すとする。

これはコスト 3 で

OIJJ
JJJJ
OOII
OOII

にすることができる.

예제 입력 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

예제 출력 2

9