Maximizing Castle Conquests

Little C is playing a strategic game where there are \(n\) castles. In each match, two players compete to capture these castles. Each player has \(m\) soldiers and must decide how many soldiers to send to each castle \(i\) such that the total number of soldiers used does not exceed \(m\). For castle \(i\), a player sends \(x_i\) soldiers.

The rule for capturing castle \(i\) is as follows: in a head‐to‐head match, if a player sends \(x_i\) soldiers and the opponent sends \(y_i\) soldiers, the player will capture castle \(i\) (gaining \(i\) points) if and only if \[ x_i > 2 \times y_i, \] where the inequality is strict.

Little C is about to play \(s\) matches against \(s\) different opponents. Importantly, he must use the same deployment strategy (the same vector \(x_1, x_2, \ldots, x_n\)) in every match. Through some means, he has acquired the strategies of the \(s\) opponents. For each match, the opponent’s deployment is given: for castle \(i\) in match \(j\), they will send \(a^j_i\) soldiers.

Thus, if Little C allocates \(x_i\) soldiers to castle \(i\), then in match \(j\) he will capture castle \(i\) if and only if \[ x_i > 2 \times a^j_i. \]

The total points obtained will be the sum over every match and every castle captured. In particular, if for castle \(i\) he wins in \(k\) out of the \(s\) matches, then he gets \(k \times i\) points from castle \(i\). Note that for each castle, Little C may choose to allocate a number of soldiers to secure wins in only a subset of matches if his chosen number of soldiers meets the condition for those games.

Your task is to help Little C determine the maximum total points he can acquire over all \(s\) matches by choosing an optimal deployment strategy \(x_1, x_2, \ldots, x_n\) under the constraint \[ \sum_{i=1}^{n} x_i \le m. \]

Input Constraints and Details:

• The first line of input contains three integers: \(n\), \(m\) and \(s\).
• Then follow \(s\) lines, each containing \(n\) integers. The \(j\)-th line represents the opponent's deployment in match \(j\): \(a^j_1, a^j_2, \ldots, a^j_n\).

Note: For each castle \(i\) and each match \(j\), in order for Little C to win castle \(i\) in match \(j\), he must allocate at least \(2 \times a^j_i + 1\) soldiers. To win in a particular castle in \(k\) matches, Little C must allocate soldiers equal at least to the \(k\)-th smallest value among \(\{2a^j_i+1\}_{j=1}^s\) (if \(k > 0\); if \(k=0\), no soldiers are needed and the score is 0).

Since the answer may not be unique, you only need to output the maximum total points Little C can achieve.

inputFormat

The first line contains three space-separated integers \(n\), \(m\) and \(s\). \(n\) is the number of castles, \(m\) is the total number of soldiers available, and \(s\) is the number of opponents (matches).

Then \(s\) lines follow. Each of these lines contains \(n\) space-separated integers. The \(j\)-th line contains \(a^j_1, a^j_2, \ldots, a^j_n\) where \(a^j_i\) denotes the soldiers the opponent sends to castle \(i\) in the \(j\)-th match.

outputFormat

Output a single integer representing the maximum total points Little C can obtain over all \(s\) matches.

sample

2 10 2
1 2
0 1

6