小Cは陣取りゲームをプレイしています。ゲームには $n$ 個の城があり、各対戦で2人のプレイヤーがこれらの城を奪い合います。各プレイヤーは $m$ 人の兵士を持っており、第 $i$ 番目の城に $a_i$ 人の兵士を派遣してその城を奪い合うことができます。ただし、派遣する兵士の合計数は $m$ を超えてはなりません。

あるプレイヤーが第 $i$ 番目の城に派遣した兵士数が、相手が派遣した兵士数の2倍を厳密に上回る場合、そのプレイヤーはその城を占領し、$i$ 点を獲得します。

今、小Cは他の $s$ 人のプレイヤーとそれぞれ1対1で対戦することになりました。この $s$ 回の対戦において、小Cが派遣する兵士の配置はすべて同じでなければなりません。小Cは他の $s$ 人のプレイヤーが使用する戦略を事前に知ることができました。小Cは、自分の合計得点を最大化するためにどのような戦略をとるべきかを知りたいと考えています。

答えが一つとは限らないため、小Cが得られる合計得点の最大値のみを出力してください。

入力

入力の1行目には、3つの正整数 $s, n, m$ が含まれており、それぞれ小C以外のプレイヤーの人数、城の数、各プレイヤーが持つ兵士の数を表します。

続く $s$ 行には、それぞれ $n$ 個の非負整数が記述されており、あるプレイヤーの戦略を表します。そのうち第 $i$ 番目の数は $a_i$ であり、そのプレイヤーが第 $i$ 番目の城に派遣する兵士数を表します。

出力

小Cが得られる最大得点を表す非負整数を1行で出力してください。

入出力例

入力 1

1 3 10
2 2 6

出力 1

3

注記 1

小Cの最適な戦略は、第 $1$ 番目の城と第 $2$ 番目の城にそれぞれ $5$ 人の兵士を派遣することです。

入力 2

2 3 10
2 2 6
0 0 0

出力 2

8

注記 2

小Cの最適な戦略の一つは、第 $1$ 番目の城に $2$ 人、第 $2$ 番目の城に $5$ 人、第 $3$ 番目の城に $1$ 人の兵士を派遣することです。

小課題

$10\%$ のデータについて、$s=1, n \le 3, m \le 10$ を満たします。

$20\%$ のデータについて、$s=1, n \le 10, m \le 100$ を満たします。

$40\%$ のデータについて、$n \le 10, m \le 100$ を満たします。

さらに $20\%$ のデータについて、$s=1$ を満たします。

$100\%$ のデータについて、以下を満たします。

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2\times 10^4$
• 各プレイヤーについて、$a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$。