from itertools import combinations
class Solution:
def __init__(self, cost, types):
self.element_info = [] # 元件
self.cost = cost # 成本
self.types = types # 类型
def getbool(self, cost, comb_list):
minrel = float('inf') # 最小可靠性的初始值
lens = self.types # 最后一位
cur_cost = 0 # 当前成本
cur_type = -1 # 当前类型
for i in range(lens):
cur_cost += comb_list[i][2] # 累加成本
next_type = comb_list[i][0] # 下一个类型
if next_type != cur_type and (comb_list[0][0] != comb_list[lens - 1][0]):
if cur_cost <= cost:
cur_type = next_type # 更新当前的类型值
cur_rel = comb_list[i][1] # 当前的可靠性
if cur_rel <= minrel:
minrel = cur_rel # 更新当前的最小可靠值
else:
return 0
else:
return 0
return minrel
def getmaxreliabily(self):
maxreliabily = 0
for elem_comb in combinations(self.element_info, self.types):
# 调用函数
reliabily = self.getbool(self.cost, elem_comb)
if reliabily >= maxreliabily:
maxreliabily = reliabily
if maxreliabily == 0:
return -1
else:
return maxreliabily
# 主函数
if __name__ == "__main__":
# 数据输入-成本-种类
inpss = input().strip().split()
fee, kind = int(inpss[0]), int(inpss[1])
# 数据输入-N 元件个数
n = int(input().strip())
# 数据输入-N 行元件信息
elem_list = [] # 元件信息列表
while True:
line = list(map(int, input().strip().split()))
if len(line) == 0:
break
else:
elem_list.append(line)
# 实例化
solution = Solution(cost=fee, types=kind)
solution.element_info = elem_list # 元件信息列表
print(solution.getmaxreliabily()) # 调用函数(打印最大的可靠值)