スクールアイドル時代から、国民的人気を誇ってきた女性アイドルグループ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行に出力せよ。
3 3 4 111 111 111 111 111 111
2
3 3 2 101 100 010 001 011 111
3
5 6 3 101101 110110 010111 110110 110111 01010 10101 11101 01011 11011 11011
4