Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

A recent glut in Chefland's markets has caused the local currency Peppercorn to devaluate sharply. (Peppercorns are getting cheaper on an average, though there could be ups and downs).

And Chef needs to rescue his wealth! Initially, he had D Peppercorns. There are N exchange kiosks in the city he lives in, where he can go and exchange his Peppercorns for a well-known stable currency, the Antarctican Dollar. For each kiosk, the exchange rate for the first M seconds of the day is known (both for buying and selling). All kiosks are arranged in a row, and to travel from the i^{th} to the j^{th} kiosk, you need to spend |i-j| seconds, and to exchange currency at any kiosk, you also need 1 second. So, starting at point of time 0 at any of the kiosks (he can get there before trading starts for the day), Chef runs from one kiosk to another to buy and sell currency. You need to find the maximum amount of Peppercorns Chef could have after the M^{th} second.

------ Note ------ 

If X is a buying rate, the kiosk will pay you X Peppercorns for 1 Antarctican Dollar.
If X is a selling rate, you will pay the kiosk X Peppercorns for 1 Antarctican Dollar.

------ Input ------ 

First line of input contains three numbers — N, M and D. N lines follow.
ith line (i = 0 … N-1) contains 2*M integers — currency rate for i^{th} kiosk. Numbers A_{i, 2j} and A_{i, 2j+1} (j = 0 … M-1) are the selling and buying rates, respectively, at the j^{th} second for the i^{th} kiosk.

------ Output ------ 

Output a single number: the maximum amount of money (in Peppercorns - in the end Chef ought to have all the money converted to local currency since it's the only valid currency in the country for financial operations) he could have after M seconds, with absolute or relative error not more than 1e-6. 
If the amount of money of any currency that Chef will own at any point of time exceeds 10^{18}, output file should contain only a single line containing  the string “Quintillionnaire” (without quotes, followed by a newline character).

------ Constraints ------ 

$1 ≤ D ≤ 10^{18}$
$1 ≤ N, M ≤ 10^{3}$
$1 ≤ A_{i, j} ≤ 10^{9}$
$A_{i, 2j} > A_{i, 2j+1} (because there are no miracles in Chefland — you’ll always pay more than what the kiosk will pay you. Otherwise, one could’ve indefinitely sold and bought and increased their money this way).$

------ Subtasks ------ 

Subtask 1 (20 points): 

$1 ≤ N ≤ 100$
$1 ≤ M ≤ 100$
$1 ≤ D ≤ 10^{3}$
$1 ≤ A_{i,j} ≤ 10^{3}$
 
Subtask 2 (30 points):

$1 ≤ N ≤ 100$
$1 ≤ M ≤ 100$
 
Subtask 3 (50 points): No additional constraints 

------ Example ------ 

Input:
3 3 5
2 1 5 3 7 6
2 1 4 3 6 5
10 9 8 7 6 5

Output:
15.0000000000

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, m, d) = [int(x) for x in input().split()]
rates = []
for _ in range(n):
	rates.append([int(x) for x in input().split()])
before_peppercorns = [d] * n
before_dollars = [0] * n
after_peppercorns = [None] * n
after_dollars = [None] * n
for t in range(m):
	for i in range(n):
		after_peppercorns[i] = max(before_dollars[i] * rates[i][2 * t + 1], before_peppercorns[i - 1] if i > 0 else 0, before_peppercorns[i + 1] if i < n - 1 else 0, before_peppercorns[i])
		after_dollars[i] = max(before_peppercorns[i] / rates[i][2 * t], before_dollars[i - 1] if i > 0 else 0, before_dollars[i + 1] if i < n - 1 else 0, before_dollars[i])
	for i in range(n):
		before_dollars[i] = after_dollars[i]
		before_peppercorns[i] = after_peppercorns[i]
amt = max(after_peppercorns)
amt2 = max(after_dollars)
if amt > 10 ** 18 or amt2 > 10 ** 18:
	print('Quintillionnaire')
else:
	print(amt)


import random
from fractions import Fraction
LIM = 10 ** 18
DE_LIM = 1
MSG = 'Quintillionnaire'
(n, m, D) = map(int, input().split())
buysell = [[[0, 0] for j in range(n)] for i in range(m)]

def solve_neq1():
	maxhave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	nexthave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	for i in range(m):
		A = max(maxhave[0][0], maxhave[0][1] * buysell[i][0][0])
		B = max(maxhave[0][1], maxhave[0][0] / buysell[i][0][1])
		nexthave[0][0] = A
		nexthave[0][1] = B
		(maxhave, nexthave) = (nexthave, maxhave)
	sol = D * max([m[0] for m in maxhave])
	sol2 = D * max([m[1] for m in maxhave])
	if sol > LIM or sol2 > LIM:
		return MSG
	return '{:.9f}'.format(float(sol.numerator) / float(sol.denominator))

def solve_ngt1():
	maxhave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	nexthave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	for i in range(m):
		A = max(maxhave[0][0], maxhave[0][1] * buysell[i][0][0])
		A = max(A, maxhave[1][0])
		B = max(maxhave[0][1], maxhave[0][0] / buysell[i][0][1])
		B = max(B, maxhave[1][1])
		nexthave[0][0] = A
		nexthave[0][1] = B
		for j in range(1, n - 1):
			A = max(maxhave[j][0], maxhave[j][1] * buysell[i][j][0])
			A = max(A, maxhave[j - 1][0])
			A = max(A, maxhave[j + 1][0])
			B = max(maxhave[j][1], maxhave[j][0] / buysell[i][j][1])
			B = max(B, maxhave[j - 1][1])
			B = max(B, maxhave[j + 1][1])
			nexthave[j][0] = A
			nexthave[j][1] = B
		A = max(maxhave[n - 1][0], maxhave[n - 1][1] * buysell[i][n - 1][0])
		A = max(A, maxhave[n - 2][0])
		B = max(maxhave[n - 1][1], maxhave[n - 1][0] / buysell[i][n - 1][1])
		B = max(B, maxhave[n - 2][1])
		nexthave[n - 1][0] = A
		nexthave[n - 1][1] = B
		(maxhave, nexthave) = (nexthave, maxhave)
	sol = D * max([m[0] for m in maxhave])
	sol2 = D * max([m[1] for m in maxhave])
	if sol > LIM or sol2 > LIM:
		return MSG
	return '{:.9f}'.format(float(sol.numerator) / float(sol.denominator))

def solve_rnd():
	maxhave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	nexthave = [[Fraction(1, 1), Fraction(0, 1)] for i in range(n)]
	LIM = Fraction(10 ** 18, D)
	for i in range(m):
		for j in range(n):
			A = max(maxhave[j][0], maxhave[j][1] * buysell[i][j][0])
			B = max(maxhave[j][1], maxhave[j][0] / buysell[i][j][1])
			if j > 0:
				A = max(A, maxhave[j - 1][0])
				B = max(B, maxhave[j - 1][1])
			if j + 1 < n:
				A = max(A, maxhave[j + 1][0])
				B = max(B, maxhave[j + 1][1])
			if A > LIM or B > LIM:
				return MSG
			nexthave[j][0] = A
			nexthave[j][1] = B
		if i % 10 == 0:
			for j in range(n):
				nexthave[j][0] = nexthave[j][0].limit_denominator(DE_LIM)
				nexthave[j][1] = nexthave[j][1].limit_denominator(DE_LIM)
		(maxhave, nexthave) = (nexthave, maxhave)
	sol = max([m[0] for m in maxhave])
	return '{:.9f}'.format(D * float(sol.numerator) / float(sol.denominator))

def solve_dbl():
	maxhave = [[1.0, 0.0] for i in range(n)]
	nexthave = [[1.0, 0.1] for i in range(n)]
	LIM = 10 ** 18 / D
	for i in range(m):
		for j in range(n):
			A = max(maxhave[j][0], maxhave[j][1] * buysell[i][j][0])
			B = max(maxhave[j][1], maxhave[j][0] / buysell[i][j][1])
			if j > 0:
				A = max(A, maxhave[j - 1][0])
				B = max(B, maxhave[j - 1][1])
			if j + 1 < n:
				A = max(A, maxhave[j + 1][0])
				B = max(B, maxhave[j + 1][1])
			if A > LIM or B > LIM:
				return MSG
			nexthave[j][0] = A
			nexthave[j][1] = B
		(maxhave, nexthave) = (nexthave, maxhave)
	sol = max([m[0] for m in maxhave])
	return '{:.9f}'.format(D * sol)
for i in range(n):
	vals = [int(x) for x in input().split()]
	assert len(vals) == 2 * m
	j = 0
	while j < m:
		buysell[j][i][1] = vals[2 * j]
		buysell[j][i][0] = vals[2 * j + 1]
		j += 1
if n == 1:
	sol = solve_neq1()
elif n * m > 100000:
	sol = solve_dbl()
else:
	sol = solve_ngt1()
print(sol)