E: Arai's - Arai's -

問題

スクールアイドル時代から、国民的人気を誇ってきた女性アイドルグループArai's。今では、たくさんの「あらい」さんが所属する大規模なグループとして、世界レベルで活躍している。そして今日、新たなるプロジェクトの始動が決定した。彼女たちは、小さなユニットをいくつか結成することで、さらなる売上の向上を試みることになったのである。

Arai'sには「荒井」さんがA人，「新井」さんがB人在籍しており、合計でA+B人の「あらい」さんからなる。新ユニットは、「荒井」さん一人と「新井」さん一人のペアで構成する。（ここで、同じ「あらい」さんが複数のユニットに所属していはいけない。）ただし、ある「荒井」さんが一部の「新井」さんのことを良く思っていないうえに、同様にある「新井」さんが一部の「荒井」さんのことを良く思っていない。「あらい」さんたちはユニットを組む際に、良く思っていない「あらい」さんをペアとして認めてくれず、一方でも認めてくれなければユニットを組むことはできない。

Arai'sのマネージャーであるあなたは、なるべくたくさんのユニットを作りたいと考えているが、メンバーの交友関係からその限界を感じていた。そこであなたは、「あらい」さんたちと個別に面談し、ユニットを組ませたい「あらい」さんについての、良い噂を聞かせることを考えた。面談をした「あらい」さんは、噂に聞いた「あらい」さんを見直し、ユニットのペアとして認めるようになる。

しかし、あなたはそれほど時間をとることができないため、最大K回までしか噂を聞かせることができない。あなたは限られた時間の中で、結成できるユニットの数を最大化しようと試みた。あなたが結成できるユニットの数の最大値を求めよ。

入力形式

A B K
a_1
...
a_A
b_1
...
b_B

1行目には、「荒井」さんの人数Aと「新井」さんの人数B (1 \≤ A, B \≤ 200でありA, Bは整数)、噂を聞かせることができる人数K (0 \≤ K \≤ 200でありKは整数)が空白区切りで与えられる。

続くA行には、それぞれ長さBの0と1のみからなる文字列が与えられる。そのうちi行目の文字列a_iのj文字目が1であるとき、i番目の「荒井」さんはj番目の「新井」さんを良く思っていない。

続くB行には、それぞれ長さAの0と1のみからなる文字列が与えられる。そのうちi行目の文字列b_iのj文字目が1であるとき、i番目の「新井」さんはj番目の「荒井」さんを良く思っていない。

出力形式

あなたが結成できるユニット数の最大値を1行に出力せよ。

入力例1

3 3 4
111
111
111
111
111
111

出力例1

2

入力例2

3 3 2
101
100
010
001
011
111

出力例2

3

入力例3

5 6 3
101101
110110
010111
110110
110111
01010
10101
11101
01011
11011
11011

出力例3

4