Nonostante la prudenza innata, le mucche hanno perso nei mutui e provano azioni. Bessie prevede prezzi: quelli di oggi di $S$ $(2 \le S \le 50)$ azioni e futuri per $D$ giorni $(2 \le D \le 10)$ totali.

Data matrice prezzi attuali e futuri per giorno $(1 \le PR_{sd} \le 1,000)$ e denaro iniziale $M$ $(1 \le M \le 200,000)$, trova acquisti/vendite ottimi per massimo guadagno alla vendita finale. Solo quantità intere di azioni, non occorre spendere tutto né nulla. Profitto massimo 500,000 garantito.

Esempio di mercato rialzista, preferito di Bessie: $S=2$, $D=3$, denaro 10. Colonne: prezzi oggi, domani, dopodomani.

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  | 
              1    10 15 15
              2    13 11 20

Per guadagnare compra azione 1 il giorno 1. Vende giorno 2 e compra subito azione 2: 4 in banca e una azione 2. Vendita finale porta 20, con banca totale 24.

Input

• Riga 1: interi con spazi $S$, $D$, $M$.
• Righe $2,\ldots,S+1$: riga $s+1$, $D$ prezzi $PR_{sd}$ dell'azione $s$ nei giorni $1,\ldots,D$.

Output

• Riga 1: massimo denaro dopo vendita nel giorno $D$.

Esempi

Input 1

2 3 10
10 15 15
13 11 20

Output 1

24

Autore: Rob Kolstad(?), 2008