В финал конкурса на получение грантов прошло три предприятия (назовем их 
). Заранее было посчитано и отображено в сводной таблице, сколько каждое предприятие сможет производить единиц товара за определенное количество единиц денежных средств.
Фонд, выдающий грант, преследует следующую цель — требуется раздать столько средств каждому из предприятий, чтобы их суммарное количество произведенных единиц товара было максимальным. Фонд может раздать все средства из гранта, либо часть.
Также фонд может выдать средства каждому предприятию лишь единожды. Например, для примера входных данных, он может выдать предприятию 
денежных средств, но не 
и 
денежных средств одновременно, несмотря на то, что фонду хватит на это денег.
В ответе укажите максимальную сумму произведенных единиц товара предприятий на деньги, полученные с гранта.
Имеется следующий набор данных:
В первой строке указано натуральное 
, 
— количество строк сводной таблицы. Во второй строке указано натуральное число 
— общий размер денежных средств фонда для распределения грантов. В третьей строке указано натуральное число 
— дискретизация распределения средств грантом. Т.е. фонд может выдать количество денежных средств одному предприятию 
, но не большее, чем число 
. В последующих 
строках подается 4 числа — шаг дискретизации, единицы товара для 
, единицы товара для 
единицы товара для 
.
В ответе укажите два числа через пробел: искомое значение для файла A и для файла B.
Пример входных данных:
4
30
10
0 0 0 0
10 34 21 33
20 47 23 40
30 67 55 90
Эти данные можно представить в виде таблицы для большей наглядности:
Например, если фонд выдаст 
10 ед. денежных средств, то 
сможет произвести 34 единицы товара.
Выходные данные для приведённого выше примера: 
Выгоднее всего оказалось выдать 
ед. денежных средств предприятию 
(а остальным не выдать ничего), т.к. в таком случае будет произведено наибольшее количество товара.
Неэффективное решение
f = open(’27A.txt’)
n = int(f.readline())
s = int(f.readline())
k = int(f.readline())
g1, g2, g3 = [], [], []
for i in range(n):
a = list(map(int, f.readline().split()))
g1.append(a[1])
g2.append(a[2])
g3.append(a[3])
ans = 0
for i in range(n):
for j in range(n):
for w in range(n):
if (i * k) + (j * k) + (w * k) <= s:
if g1[i] + g2[j] + g3[w] > ans:
ans = g1[i] + g2[j] + g3[w]
print(ans)
Эффективное решение
f = open(’27B.txt’)
n = int(f.readline())
s = int(f.readline())
k = int(f.readline())
g1, g2, g3 = [], [], []
for i in range(n):
a = list(map(int, f.readline().split()))
g1.append(a[1])
g2.append(a[2])
g3.append(a[3])
g = [g1, g2, g3]
ans = [[0] * n for i in range(n)]
F = [[0] * n for i in range(len(g))]
F[0] = g[0].copy()
for k in range(1, 3):
for i in range(n):
for j in range(n):
if i - j >= 0:
ans[i][j] = g[k][j] + F[k - 1][i - j]
for i in range(n):
F[k][i] = max(ans[i])
print(max(F[2]))