Si vius en un poble, segur que hi estàs d'acord: no hi ha millor pla per a un dissabte al matí que anar a Barcelona i veure com els turistes (o guiris) t’ocupen tot l’espai al metro mentre t’adones que vas en direcció contrària.

Per sort, avui resoldrem aquest problema i ajudarem els guiris a passar més temps a l’aire lliure. Un guiri vol visitar el màxim nombre de llocs emblemàtics de Barcelona en un temps limitat. Per això, se li donarà:

1. Un mitjà de transport inicial: Pot ser taxi, bici o peu.
2. Una matriu de dimensions N x M: Cada casella representa un lloc emblemàtic i conté el temps (en hores) necessari per visitar-lo.
3. Un nombre T: El temps total disponible del guiri.

Els turistes tenen una manera peculiar de decidir la seva ruta: sempre escullen el lloc que es visita més ràpidament, independentment de la seva posició. També cal comentar que depenent del tipus de transport el temps serà diferent:

• Peu: El temps es manté igual (1:1).
• Bici: El temps de cada lloc es redueix a 2/3 del seu valor original.
• Taxi: El temps de cada lloc es redueix a 1/3 del seu valor original.

L'objectiu és determinar el nombre màxim de llocs que el guiri pot visitar dins del temps T.

Consideracions

• La matriu no pot contenir números decimals.
• Sempre es triarà el lloc que es pugui visitar en menys temps primer.

Entrada

Un String del transport que utilitzarà el guiri, els files i columnes de la matriu, el contingut de la matriu i el nombre d'hores que té el guiri per aconseguir el seu objectiu.

Sortida

El nombre de llocs que ha aconseguit anar

Exemple d'Entrada 1

taxi
3 3
1 2 3
4 5 6
7 8 9
10

Exemple de Sortida 1

7

Exemple d'Entrada 2

bici
4 5
3 7 2 8 4
6 1 9 5 3
2 4 6 1 7
8 3 5 2 6
15

Exemple de Sortida 2

9