P5322 [BJOI2019] Troop Deployment

Xiao C is playing a troop deployment game. In the game, there are $n$ castles, and each match is a battle between two players competing for these castles. Each player has $m$ soldiers, and may send $a_i$ soldiers to the $i$-th castle to compete for it, as long as the total number of soldiers sent does not exceed $m$. If the number of soldiers a player sends to the $i$-th castle is **strictly** greater than twice the number sent by the opponent, then the player occupies this castle and gains $i$ points. Now Xiao C is going to play head-to-head matches against another $s$ players. The troop deployment plan used in these $s$ matches must be the same. Through some means, Xiao C has learned the strategies that the other $s$ players are going to use, and he wants to know what strategy he should use to maximize his total score. Since the answer may not be unique, you only need to output the maximum possible total score of Xiao C.

The first line contains three positive integers $s,n,m$, representing the number of players other than Xiao C, the number of castles, and the number of soldiers each player has. The next $s$ lines each contain $n$ non-negative integers, describing one player’s strategy. The $i$-th number $a_i$ means the number of soldiers this player sends to the $i$-th castle.

Output one line with one non-negative integer, representing the maximum score Xiao C can obtain.

**Explanation for Sample 1:** Xiao C’s best strategy is to send $5$ soldiers to the $1$-st castle and $5$ soldiers to the $2$-nd castle. **Explanation for Sample 2:** One of Xiao C’s best strategies is to send $2$ soldiers to the $1$-st castle, $5$ soldiers to the $2$-nd castle, and $1$ soldier to the $3$-rd castle. **Constraints:** For $10\%$ of the testdata: $s=1,n \le 3,m \le 10$. For $20\%$ of the testdata: $s=1,n \le 10,m \le 100$. For $40\%$ of the testdata: $n \le 10,m \le 100$. For another $20\%$ of the testdata: $s=1$. For $100\%$ of the testdata: $1 \le s \le 100$. $1 \le n \le 100$. $1 \le m \le 20000$. For each player, $a_i \ge 0$, and $\sum\limits_{i=1}^n a_i \le m$. Translated by ChatGPT 5