You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 n 座城市，国王们通过打仗互相争夺这些城市。如果一个国王向第 i 座城市派遣的兵团数严格​大于对手派遣兵团数的两倍，那么这个国王就占领了这座城市，获得 i 分。

聪明的吉吉国王即将和其他 s 个国王两两对战，他通过某些途径得知了其他 s 个国王即将使用的策略，吉吉国王有 m 个兵团可以操控，他想知道他应该使用什么分兵策略来最大化自己的总分。（注意这 s 场对决的派遣兵团方案必须相同）.

请你编程输出吉吉国王能获得的最大总分。

输入格式

输入第一行包含三个正整数 $s,n,m$，分别表示除了吉吉国王以外的国王人数、城市数和每个国王拥有的士兵数。

接下来 $s$ 行，每行 $n$ 个非负整数，表示一个国王的策略，其中第 $i$ 个数 $a_i$ 表示这个国王向第 $i$ 座城市派遣的士兵数。

输出格式

输出一行一个非负整数，表示吉吉国王获得的最大得分。

1 3 10
2 2 6

3

2 3 10
2 2 6
0 0 0

8

提示

样例1解释：

吉吉国王的最佳策略为向第 $1$ 座城市和第 $2$ 座城市各派遣 $5$ 个士兵。

样例2解释：

吉吉国王的最佳策略之一为向第 $1$ 座城市派遣 $2$ 个士兵，向第 $2$ 座城市派遣 $5$ 个士兵，向第 $3$ 座城市派遣 $1$ 个士兵。

数据范围

对于10% 的数据：s=1,n≤3,m≤10

对于另10% 的数据：s=1,n≤10,m≤100

对于另20% 的数据：1≤s≤10,n≤10,m≤100

对于另外20% 的数据： s=1，1≤n≤100; 1≤m≤2000.

对于 100% 的数据：1≤s≤100; 1≤n≤100; 1≤m≤20000.

数据保证对于每个国王ai​≥0，∑​ai​≤m