cho.sh

JOI Flag

일부 칸에만 문자가 적힌 2^K × 2^K 격자가 주어질 때, 문자를 고치는 비용 1을 최소로 써서 사분면 재귀 구조로 정의된 레벨 K JOI Flag를 완성하는 최소 비용을 구한다.

어려움8분할 정복동적 계획법재귀구현아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

あなたは，日本情報オリンピックの新しい旗として，レベル 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) はすべて異なる．