P5662 [CSP-J 2019] Souvenirs

Xiaowei suddenly gains a superpower: he knows the prices of $N$ kinds of souvenirs for each of the next $T$ days. The price of a souvenir means the number of coins needed to buy one unit of that souvenir, and also the number of coins you get back by selling one unit of that souvenir. Each day, Xiaowei can perform the following two types of transactions an **unlimited** number of times: 1. Choose any souvenir; if he has enough coins, buy that souvenir at today’s price. 2. Sell any souvenir he is holding, and exchange it for coins at today’s price. The coins obtained from selling souvenirs can be used **immediately** to buy souvenirs. Souvenirs bought on the same day can also be **sold on the same day** for coins. Of course, he may also keep holding souvenirs. After $T$ days, Xiaowei’s superpower disappears. Therefore, he will definitely sell **all** souvenirs on day $T$ to get coins back. Xiaowei currently has $M$ coins. He wants to have as many coins as possible after his superpower disappears.

The first line contains three positive integers $T, N, M$, separated by single spaces, representing the number of future days $T$, the number of souvenir types $N$, and the number of coins Xiaowei currently has $M$. The next $T$ lines each contain $N$ positive integers, separated by single spaces. On line $i$, the $N$ integers are $P_{i,1}, P_{i,2}, \dots, P_{i,N}$, where $P_{i,j}$ denotes the price of the $j$-th type of souvenir on day $i$.

Output only one line containing one positive integer, representing the maximum number of coins Xiaowei can have after his superpower disappears.

**Sample 1 Explanation** The best strategy is: On day 2, spend all $100$ coins to buy $5$ units of souvenir $1$. On day 3, sell the $5$ units of souvenir $1$ to get $125$ coins. On day 4, buy $6$ units of souvenir $1$, with $5$ coins remaining. On day 6, you must sell all souvenirs to get $300$ coins back; together with the $5$ coins left from day 4, this is a total of $305$ coins. After the superpower disappears, Xiaowei can have at most $305$ coins. **Sample 2 Explanation** The best strategy is: On day 1, spend all coins to buy $10$ units of souvenir $1$. On day 2, sell all units of souvenir $1$ to get $150$ coins, then buy $8$ units of souvenir $2$ and $1$ unit of souvenir $3$, with $1$ coin remaining. On day 3, you must sell all souvenirs to get $216$ coins back; together with the $1$ coin left from day 2, this is a total of $217$ coins. After the superpower disappears, Xiaowei can have at most $217$ coins. **Constraints** For $10\%$ of the testdata, $T = 1$. For $30\%$ of the testdata, $T \leq 4$, $N \leq 4$, $M \leq 100$, and all prices satisfy $10 \leq P_{i,j} \leq 100$. For another $15\%$ of the testdata, $T \leq 100$ and $N = 1$. For another $15\%$ of the testdata, $T = 2$ and $N \leq 100$. For $100\%$ of the testdata, $T \leq 100$, $N \leq 100$, $M \leq 10^3$, and all prices satisfy $1 \leq P_{i,j} \leq 10^4$. The testdata guarantees that at any moment, the number of coins Xiaowei has cannot exceed $10^4$. # Input Format # Output Format # Hint Translated by ChatGPT 5