Problem C
卒業式

学校の管理者は、今年の卒業式に関する問題に遭遇しました。 卒業式では、生徒は$N$列に並び、各列には$M$人の生徒がいます。 管理者は、卒業式をできるだけカラフルなものにしたいと思っているので、生徒たちに色違いの帽子を配ります。

見栄えをよくするためには、同じ順序に並んでいる生徒全員が同じ色の帽子を持っていることが大切です。 誰もが取り残されていると感じないように、同じクラスの生徒全員が同じ帽子の色を持っていることも重要です。 各生徒の列と順序はすでに決定されていますが、帽子の色は決定されていません。 卒業式が少しでも華やかなものになるように生徒に帽子の色を割り振る方法について、管理者から協力を依頼されました。

指定された学生の並びに対して、学生に割り当てることができる帽子の色の最大数を計算するプログラムを書いてください。

入力

1行目には、整数$N$, $M$ ($1 \leq N, M \leq 700$) と $K$ ($1 \leq K \leq 26$) が含まれ、それぞれ列数、列の人数、クラス数を表しています。

次の $N$ 行には、それぞれ $M$ 文字が含まれ、生徒の並び順を表しています。 $i$ 行目の $j$ 文字目はアルファベットのAから$K$番目の文字のいずれかであり、これは、$i$列めの$j$番目の生徒が属するクラスを表します。 各クラスに生徒は1人以上います。

出力

1つの整数で、生徒に割り当てることができる帽子の色の最大数を出力します。 このとき、列の同じ順序の生徒は同じ色の帽子を、同じクラスの生徒にも同じ色の帽子を割り当てる必要があります。

得点

サンプルの説明

最初の例では、2番目にAクラスの生徒が1人、Bクラスの生徒が1人います。 この2人とも帽子の色が同じでなければならないので、Aクラスの全員がBクラスの全員と同じ色の帽子を持っていなければなりません。 結果として全ての生徒が同じ色の帽子を持っていなければならないため、答えは$1$となります。

2番目の例では、AクラスとBクラスは先頭に生徒がいるため同じ色の帽子を持っていなければなりません。 一方、Cクラスは異なる色にすることができます。したがって、答えは$2$となります。

3番目の例では、異なるクラスで同じ順序にいる生徒がいないため、各クラスに別の色を割り当てることができます。したがって、答えは$3$になります。

最後の例では、A, B, Cクラスの生徒全員に1つめの色を、D, Eクラスの生徒全員に2つめの色を割り当てることができます。したがって、答えは$2$になります。

2 3 2
AAB
ABB

1

2 2 3
AC
BC

2

2 3 3
ABC
ABC

3

3 5 5
ABECE
BCDAE
CADBD

2