Maximizing Coins with Souvenir Trading

You are given T days, N types of souvenirs, and an initial amount of M coins. For each day i (with \(1 \le i \le T\)), you are given the prices for each souvenir type \(j\) (\(1 \le j \le N\)). The price of a souvenir on day \(i\) is expressed as a pair of numbers: the buying price \(a_{i,j}\) and the selling price \(b_{i,j}\).

Every day you are allowed to perform the following two operations an unlimited number of times:

1. Choose any souvenir type \(j\). If you have at least \(a_{i,j}\) coins, you can buy one unit of that souvenir by paying \(a_{i,j}\) coins.
2. Sell any souvenir you own of any type \(j\) to receive \(b_{i,j}\) coins.

The coins obtained from selling can be used immediately to make further purchases on the same day, and souvenirs bought on the same day can also be sold immediately. You may also hold souvenirs between days. However, after the T-th day your superpower disappears, so you must sell all the souvenirs you own on day \(T\) to convert them back into coins.

Your objective is to maximize the number of coins you have at the end of day \(T\). Note that in a transaction you must use the whole coins you have: if you have \(X\) coins and decide to buy a souvenir with buying price \(a\), then you can buy \(\lfloor X/a \rfloor\) units and will have \(X \bmod a\) coins left over; after selling them at price \(b\), you will get a total of \(\lfloor X/a \rfloor \times b + (X \bmod a)\) coins.

Input (Format):

T N M
a1,1 b1,1 a1,2 b1,2 ... a1,N b1,N
...
 aT,1 bT,1 aT,2 bT,2 ... aT,N bT,N

Here, day i provides 2\(N\) integers. For each souvenir type \(j\), \(a_{i,j}\) is the number of coins required to buy one unit on day \(i\), and \(b_{i,j}\) is the number of coins you gain by selling one unit on day \(i\).

Output (Format):

X

Output the maximum number of coins you can have after day \(T\).

Note: You may execute transactions on different days. In a transaction, if you buy on day \(i\) (using the prices given on day \(i\)) and sell on a later day \(j\) (using the prices on day \(j\)), your coin count becomes:

[ X' = \left\lfloor \frac{X}{a_{i,j}} \right\rfloor \times b_{j,j} + \left(X \bmod a_{i,j}\right), ]

and you are allowed to make multiple such transactions (non‐overlapping in time) to maximize your final coin count.

inputFormat

The first line contains three integers \(T\), \(N\) and \(M\) (the number of days, the number of souvenir types, and the initial coin count respectively).

Then T lines follow. The i-th line contains 2\(N\) integers: \(a_{i,1}~b_{i,1}~a_{i,2}~b_{i,2} \ldots a_{i,N}~b_{i,N}\), where \(a_{i,j}\) is the buying price and \(b_{i,j}\) is the selling price of the j-th souvenir on day i.

outputFormat

Output a single integer \(X\), which is the maximum number of coins you can have after day \(T\).

sample

3 1 10
10 10
5 6
6 7

14