勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。
勇者背包内共有编号为 0 ~ 4 的五种食材，其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第 i 种料理需要第 j 种食材的数量，而 attribute[i] = [x,y] 表示第 i 道料理的美味度 x 和饱腹感 y。
在饱腹感不小于 limit 的情况下，返回勇者可获得的最大美味度。如果无法满足饱腹感要求，则返回 -1。
注意：每种料理只能制作一次。
示例 1：
输入：（依次输入materials、cookbooks、attribute、limit的值）
[3,2,4,1,2]
[[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]
[[3,2],[2,4],[7,6]]
5
输出：
7
解释： 食材数量可以满足以下两种方案： 方案一：制作料理 0 和料理 1，可获得饱腹感 2+4、美味度 3+2 方案二：仅制作料理 2， 可饱腹感为 6、美味度为 7 因此在满足饱腹感的要求下，可获得最高美味度 7
示例 2：
输入：（依次输入materials、cookbooks、attribute、limit的值）
[10,10,10,10,10]
[[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]]
[[5,5],[6,6],[10,10]]
1
输出：
11
解释：通过制作料理 0 和 1，可满足饱腹感，并获得最高美味度 11
提示：
materials.length == 5
1 <= cookbooks.length == attribute.length <= 8
cookbooks[i].length == 5
attribute[i].length == 2
0 <= materials[i], cookbooks[i][j], attribute[i][j] <= 20
1 <= limit <= 100
def perfectMenu(materials, cookbooks, attribute, limit):
def has_materials(materials):
for material in materials:
if material < 0:
return False
return True
def can_cookbooks(materials, cookbook):
materials = [materials[i] - cookbook[i] for i in range(num_material)]
return materials
def back_trace(materials, x, y, deep):
if y >= limit:
ans.append(x)
if deep < num_attribute:
back_trace(materials[:], x, y, deep + 1)
materials = can_cookbooks(materials, cookbooks[deep])
if has_materials(materials):
back_trace(materials[:], x+attribute[deep][0], y+attribute[deep][1], deep + 1)
ans = [-1]
num_attribute = len(attribute)
num_material = len(materials)
back_trace(materials, 0, 0, 0)
return max(ans)
materials = eval（input())
cookbooks = eval（input())
attribute = eval（input())
limit = eval（input())
print(perfectMenu(materials, cookbooks, attribute, limit))