Question

HELP ME ASAPPPPPPP!!

The player cards that Neo can currently purchase are given the following information: position, overall, price, salary, and player name.


Every player's name is different. There can be multiple cards of the same player, and in this case, the position is always the same.


Neo guns a new team

It is intended to consist of 11 members. For each position, there can be exactly 1 GK, 3 to 5 DFs, 2 to 5 MFs, and 1 to 4 FWs. You cannot select the same player multiple times.


There are two types of costs. There is a cost that must be paid when a player is first brought in, that is, the price of the player card, and a cost that must be paid to the player periodically, that is, the salary of the player card. Due to budget limitations, the sum of the prices of the player cards to be purchased cannot exceed Neo's money M, and the league's regulation prevents the sum of the salaries from exceeding 120.


For example, suppose there are 16 player cards and Neo's money M is 60, as shown in the table below.


No. Position Overall Price Salary Name

1 GK 20 3 5 na

2 GK 30 5 10 nb

3 df 10 2 5 nc

4 DF 10 3 5 nc

5 DF 15 3 10 nd

6 df 15 4 10 ne

7 df 20 5 15 nf

8 df 20 6 15 ng

9 M-F 15 2 5 nh

10 M F 15 2 5 ni

11 M-F 20 3 10 nj

12 M F 20 4 15 nk

13 M-F 20 5 15 nl

14 M-F 20 6 20 nl

15 FW 20 10 20 nm

16 FW 30 15 30 nm


Player 2's card as GK, Player 3, 5, 6, 7 card as DF, Player 9, 10, 11, 12, 13 card as MF, and Player 15 card as FW The sum makes up a great team. At this time, 1 GK, 4 DFs, 5 MFs, and 1 FW satisfies Joseon. The sum of the prices is 45, the sum of the salaries is 120, and the sum of the overall is 200.


Write a program that calculates the maximum sum of possible overalls when a team of 11 players is formed given N player card information and satisfying the above constraints.


input format

In the first line, the number N of player cards and the number M representing Neo's money are given, separated by spaces. (11≤N≤500;20≤M≤120)

Information on card i of the following N lines is given. In each week, a string representing the position of the player on card 1, an integer A(i) representing the overall, B(i) representing the price, C(i) representing the salary, and a string representing the player's name are given as blanks. (1≤A(i)≤100;1≤B≤M;1≤C(i)≤120)

The string representing the position is one of GK, DF, MF, and FW, and all players' names are strings of 10 or less English alphabets and lowercase letters.



output format

In the first line, the maximum value of the overall sum of the player cards selected when forming the team is output. If there is no way to form a team, output −1.


input example

16 60

GK 20 3 5 na

GK 30 5 10 nb

DF 10 2 5 nc

DF 10 3 5 nc

DF 15 3 10 nd

D-F 15 4 10 ne

DF 20 5 15 nf

DF 20 6 15 ng

M-F 15 2 5 nh

M-F 15 2 5 ni

M-F 20 3 10 nj

M-F 20 4 15 n.k.

M-F 20 5 15 nl

M-F 20 6 20 nl

FW 20 10 20 nm

FW 30 15 30 nm



output example

200


example description

The input example given is the same as described in the problem body.


If you input an input example, the correct answer should come out according to the output example, and it should come out correctly even if you give another type of correct answer.

N≤20, all cards have the same price, and all cards have the same salary. Also, multiple cards from one player are not given.


Please write the code in python as possible.

Answer 1

Sure, here's a Python program to solve the given problem:\

----------------------------------------------------------------------------------------------------------

Python -

----------------------------------------------------------------------------------------------------------

def dfs(players, position_counts, overall_sum, price_sum, salary_sum, index, max_overall, max_overall_sum):

if index == len(players):

if position_counts["GK"] == 1 and 3 <= position_counts["DF"] <= 5 and 2 <= position_counts["MF"] <= 5 and position_counts["FW"] == 1 and price_sum <= M and salary_sum <= 120:

max_overall_sum[0] = max(max_overall_sum[0], overall_sum)

return

dfs(players, position_counts, overall_sum, price_sum, salary_sum, index + 1, max_overall, max_overall_sum)

player = players[index]

position, overall, price, salary = player

if position_counts[position] < 5:

position_counts[position] += 1

dfs(players, position_counts, overall_sum + overall, price_sum + price, salary_sum + salary, index + 1, max_overall, max_overall_sum)

position_counts[position] -= 1

N, M = map(int, input().split())

players = []

for _ in range(N):

position, overall, price, salary, name = input().split()

overall, price, salary = int(overall), int(price), int(salary)

players.append((position, overall, price, salary))

max_overall_sum = [0]

dfs(players, {"GK": 0, "DF": 0, "MF": 0, "FW": 0}, 0, 0, 0, 0, 11, max_overall_sum)

print(max_overall_sum[0] if max_overall_sum[0] > 0 else -1)

----------------------------------------------------------------------------------------------------------