Problem:


長年の研究の末、イクタ君は未来予知能力を手に入れた！　彼がこの研究に費やした時間や金銭は莫大なものであったが、ついに報われる時がやってきたのだ。手始めに金銭を取り戻すため、イクタ君は株式投資を始めることにした。

イクタ君は現在株式は全く保有しておらず、 x 円を所持している。彼が投資対象に定めた株式は n 種類で、それらについて今日から d 日分の株価を予知することに成功した。その結果、驚くべきことに今日から d 日間は日中の株価変動が全くないことが判明した。つまり、今日を1日目としたときの i （1 ≤ i ≤ d）日目の株式 j （1 ≤ j ≤ n）の株価 pi,j 円がわかっている。イクタ君はそれぞれの日に自由に株式を売買できる。すなわち、任意の時点で以下の操作（購入・売却）を任意の順番で任意の回数行える。ただし、各操作の前後での所持金と株式の保有単位数は非負整数でなければならない。

 購入 : i 日目に、株式の種類 j （1 ≤ j ≤ n）を一つ選び、所持金 pi,j 円を支払い1単位の株式 j を得る。

 売却 : i 日目に、株式の種類 j （1 ≤ j ≤ n）を一つ選び、1単位の株式 j を支払い pi,j 円を得る。

（彼が研究に没頭する間に証券取引システムは大きな発達を遂げ、取引手数料はかからなくなった。）

イクタ君は大学で情報科学を修めていたが、未来予知研究に明け暮れるすえに大学で学んだことをすべて忘れてしまっていた。そんな彼の代わりに最終日の所持金を最大化するプログラムを書いてあげてほしい。

Input

入力は以下の形式で与えられる。

n d x 
p1,1 ... p1,n
...
pd,1 ... pd,n

 n : 株式の種類数

 d : 日数

 x : 1日目の所持金

 pi,j : i 日目の銘柄jの株価（今日を1日目とする）

Constraints

入力中の各変数は以下の制約を満たす整数である。

 1 ≤ n ≤ 10

 1 ≤ d ≤ 10

 1 ≤ x, pi,j ≤ 105

 最終日の所持金が 105 以下となることが保証されている。

Output

最適に投資した場合の最終日の所持金を1行に出力せよ。

Sample Input 1

2 2 5
3 2
5 4

Output for the Sample Input 1

9

例えば、それぞれの株式を1単位ずつ購入します。

Sample Input 2

1 2 5
6
10000

Output for the Sample Input 2

5

 1単位より小さい取引はできません。小口投資家の悲哀です。

Sample Input 3

2 3 5
4 5
6 3
8 5

Output for the Sample Input 3

11

 1日目は1種類目の株式に、2日目は2種類目の株式に投資します。

Sample Input 4

3 3 10
10 9 6
8 7 3
7 5 1

Output for the Sample Input 4

10

 景気が悪い時もあります。



Sample input:
2 2 5
3 2
5 4


Sample output:
9

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddict
n, d, x = map(int,raw_input().split(" "))
p = [map(int,raw_input().split(" ")) for i in range(d)]
for i in range(d-1):
	profit = ddict(int)
	for j in range(n):
		tmp = p[i+1][j] - p[i][j]
		if tmp > 0 and p[i][j] <= x and tmp > profit[p[i][j]]:
			profit[p[i][j]] = tmp
	key_value = profit.items()
	dp = [0 for i in range(x+1)]
	for j in range(1,x+1):
		dp[j] = max([0 if j < cost else dp[j-cost] + prof for cost, prof in key_value]+[dp[j-1]])
	x += dp[x]
print x

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddict
n, d, x = map(int,raw_input().split(" "))
p = [map(int,raw_input().split(" ")) for i in range(d)]
for i in range(d-1):
	profit = ddict(int)
	for j in range(n):
		tmp = p[i+1][j] - p[i][j]
		if tmp > 0 and p[i][j] <= x and tmp > profit[p[i][j]]:
			profit[p[i][j]] = tmp
	key_value = profit.items()
	dp = [0 for i in range(x+1)]
	for j in range(1,x+1):
		dp[j] = max([dp[(j-cost) * (j >= cost)] + prof * (j >= cost) for cost, prof in key_value]+[dp[j-1]])
	x += dp[x]
print x

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddict
n, d, x = map(int,raw_input().split(" "))
p = [map(int,raw_input().split(" ")) for i in range(d)]
for i in range(d-1):
	profit = ddict(int)
	for j in range(n):
		tmp = p[i+1][j] - p[i][j]
		if tmp > 0 and p[i][j] <= x and tmp > profit[p[i][j]]:
			profit[p[i][j]] = tmp
	key_value = profit.items()
	dp = [0 for j in range(x+1)]
	for j in range(1,x+1):
		dp[j] = max([dp[(j-cost) * (j >= cost)] + prof * (j >= cost) for cost, prof in key_value]+[dp[j-1]])
	x += dp[x]
print x

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n,d,x = map(int,input().split())
weights = []
for i in range(d):
    weights.append(list(map(int,input().split())))

prices = []
for i in range(d-1):
    prices.append([weights[i+1][j] - weights[i][j] for j in range(n)])

dp = [False for i in range(10**5+1)]
dp[0] = 0
bag = x
for i in range(d-1):
    for j in range(n):
        for k in range(10**5):
            if weights[i][j] + k < 10**5+1 and dp[k] is not False:
                dp[k+weights[i][j]] = max(dp[k+weights[i][j]],dp[k] + prices[i][j])
    bag = max(dp[:bag]) + bag

print(bag)

Submission status: Wrong Answer

Solution code:
n, d, x = map(int, raw_input().split())
P = [map(int, raw_input().split()) for i in xrange(d)]
dp = [x]+[0]*(d-1)
for i in xrange(d-1):
    for k in xrange(i+1, d):
        dp[k] = max(dp[k], dp[i])
    for j in xrange(n):
        for k in xrange(i+1, d):
            dp[k] = max(dp[k], dp[i]+(dp[i]/P[i][j])*(P[k][j]-P[i][j]))
print dp[-1]

Submission status: Wrong Answer

Solution code:
N, D, X = map(int, input().split())
INF = 10 ** 5
dp = [0] * (INF + 1)
P = [tuple(map(int, input().split())) for _ in range(D)]
for i in range(X + 1):
    dp[i] = i
ans = X
for d in range(D - 1):
    for i in range(N):
        for j in reversed(range(P[d][i], ans + 1)):
            if 0 <= j + P[d + 1][i] - P[d][i] <= INF:
                dp[j + P[d + 1][i] - P[d][i]] = j + P[d + 1][i] - P[d][i]
                ans = max(ans, j + P[d + 1][i] - P[d][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, x = map(int, input().split())
plst = [list(map(int, input().split())) for _ in range(d)]
for i in range(d - 1):
  max_pro = 0
  for j in range(n):
    pro = (plst[i + 1][j] - plst[i][j]) * (x // plst[i][j])
    max_pro= max(pro, max_pro)
  x += max_pro

print(x)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
n, d, x = map(int,raw_input().split(" "))
p = [map(int,raw_input().split(" ")) for i in range(d)]
for i in range(d-1):
	profit = ddict(int)
	for j in range(n):
		tmp = p[i+1][j] - p[i][j]
		if tmp > 0 and p[i][j] <= x and tmp > profit[p[i][j]]:
			profit[p[i][j]] = tmp
	dp = [0 for j in range(x+1)]
	for cost, prof in profit.iteritems():
		for j in range(cost,x+1):
			dp[j] = max(dp[j], dp[j-1], dp[j-cost]+prof)
	x += dp[x]
print x

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n,d,x = map(int,input().split())
weights = []
for i in range(d):
    weights.append(list(map(int,input().split())))

prices = []
for i in range(d-1):
    prices.append([weights[i+1][j] - weights[i][j] for j in range(n)])

bag = x
for i in range(d-1):
    dp = [False for i in range(bag+1)]
    dp[0] = 0
    for j in range(n):
        for k in range(bag):
            if weights[i][j] + k < bag+1 and dp[k] is not False:
                dp[k+weights[i][j]] = max(dp[k+weights[i][j]],dp[k] + prices[i][j])

    bag += max(dp[:bag+1])

print(bag)

Submission status: Accepted

Solution code:
I=input
n,d,x=map(int,I().split())
w=[list(map(int,I().split()))for i in range(d)];d-=1
p=[[w[i+1][j]-w[i][j]for j in range(n)]for i in range(d)]
b=x
for i in range(d):
    dp = [False for j in range(b+1)]
    dp[0]=0
    for j in range(n):
        for k in range(b):
            if w[i][j]+k<b+1 and id(dp[k])!=False:
                dp[k+w[i][j]]=max(dp[k+w[i][j]],dp[k]+p[i][j])
    b+=max(dp[:b+1])
print(b)

Submission status: Accepted

Solution code:
import sys

def calc(x, n, p1, p2):
    dp = []
    for i in range(n):
        dp.append( [0] * (x + 1) )

    pocket = x
    for i in range(n):
        for j in range(x + 1):
            dp[i][j] = dp[i - 1][j]
            if j - p1[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i][j - p1[i]] + p2[i])
            pocket = max(pocket, (x - j) + dp[i][j])

    return pocket

def main():
    n,d,x = map(int, sys.stdin.readline().split())

    pp = []
    for i in range(d):
        pp.append( list(map(int,sys.stdin.readline().split())) )

    curr_x = x
    for i in range(d - 1):
        curr_x = calc(curr_x, n, pp[i], pp[i + 1])

    print(curr_x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    n,d,x = map(int, sys.stdin.readline().split())

    pp = []
    for i in range(d):
        pp.append( list(map(int,sys.stdin.readline().split())) )

    dp = [0] * 100001
    curr_x = x
    for k in range(d - 1):
        next_x = curr_x
        for i in range(curr_x + 1):
            dp[i] = 0
        for i in range(n):
            for j in range(curr_x + 1):
                if j - pp[k][i] >= 0:
                    dp[j] = max(dp[j], dp[j - pp[k][i]] + pp[k + 1][i])
                next_x = max(next_x, (curr_x - j) + dp[j])
        curr_x = next_x

    print(curr_x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, D, X = map(int, input().split())
INF = 10 ** 5
dp = [0] * (INF + 1)
P = [tuple(map(int, input().split())) for _ in range(D)]
for i in range(X + 1):
    dp[i] = i
ans = X
for d in range(D - 1):
    for i in range(ans + 1):
        dp[i] = i
    tmp = ans
    for i in range(N):
        for j in range(P[d][i], ans + 1):
            dp[j] = max(dp[j], dp[j - P[d][i]] + P[d + 1][i])
            tmp = max(tmp, dp[j])
    ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,d,x = LI()
        a = [LI() for _ in range(d)]
        for i in range(d-1):
            t = [0] * (x+1)
            t[x] = x
            for j in range(n):
                if a[i][j] >= a[i+1][j]:
                    continue
                aj = a[i][j]
                ak = a[i+1][j] - aj
                for k in range(x,aj-1,-1):
                    if t[k-aj] < t[k] + ak:
                        t[k-aj] = t[k] + ak
            x = max(t)

        rr.append(x)
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
def get_pro(w, v):
  """
  dp[a][b] ... a番目、金額bまでで作れる最高の利益
  dp[a][b] = max(dp[a - 1][b], dp[a - 1][b - w * k] + v * k)
  """
  dp = [0] * (x + 1)
  for a in range(n):
    wa = wlst[a]
    va = vlst[a]
    for b in range(wa, x + 1):
      dp[b] = max(dp[b], dp[b - wa] + va)
  return dp[x]

n, d, x = map(int, input().split())
plst = [list(map(int, input().split())) for _ in range(d)]
for i in range(d - 1):
  vlst = [plst[i + 1][j] - plst[i][j] for j in range(n)]
  wlst = [plst[i][j] for j in range(n)]
  x += get_pro(wlst, vlst)
print(x)