짠돌이 구단주

네오는 피파 온라인 게임을 좋아한다. 오랫동안 사용하던 팀을 팔고 새로운 팀을 구성하려 한다.

네오가 현재 구매할 수 있는 선수 카드들에는 다음과 같은 정보가 주어진다: 포지션, 오버롤, 가격, 급여, 선수의 이름.

모든 선수의 이름은 다르다. 같은 선수의 카드가 여러 개 존재할 수 있고 이 경우 포지션은 항상 동일하다.

네오는 새로운 팀을 총 $11$ 명으로 구성하고자 한다. 포지션별로 GK는 정확히 $1$ 명, DF는 $3$ 명 이상 $5$ 명 이하, MF는 $2$ 명 이상 $5$ 명 이하, FW는 $1$ 명 이상 $4$ 명 이하로 구성할 수 있다. 같은 선수를 여러 번 선택할 수 없다.

두 가지 종류의 비용이 있다. 처음 선수를 데려올 때 지급해야 하는 비용, 즉, 선수 카드의 가격이 있고, 주기적으로 선수에게 지급해야 하는 비용, 즉, 선수 카드의 급여가 있다. 예산의 한계로 구매하려는 선수 카드의 가격의 합은 네오가 가진 돈 $M$을 넘을 수 없고, 리그의 규제로 급여의 합은 $120$을 넘을 수 없다.

예를 들어서, 다음 표와 같이 $16$ 개의 선수 카드가 있고, 네오가 가진 돈 $M$이 $60$이라고 하자.

GK로 $2$번 선수 카드를, DF로 $3$, $5$, $6$, $7$번 선수 카드를, MF로 $9$, $10$, $11$, $12$, $13$번 선수 카드를, FW로 $15$번 선수 카드를 선택하면 오버롤의 합이 최대인 팀을 구성한다. 이때, GK는 $1$ 명, DF는 $4$ 명, MF는 $5$ 명, FW는 $1$ 명으로 조건을 만족한다. 가격의 합은 $45$, 급여의 합은 $120$, 오버롤의 합은 $200$이다.

$N$ 개의 선수 카드 정보가 주어지고, 위의 제약 조건을 만족하면서 $11$ 명으로 이루어진 팀을 구성할 때, 가능한 오버롤의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 선수 카드의 수 $N$과 네오가 가진 돈을 나타내는 수 $M$이 공백으로 구분되어 주어진다. ($11 \le N \le 500;$ $20 \le M \le 120$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번 카드에 대한 정보가 주어진다. 각 줄은 $i$ 번 카드의 선수의 포지션을 나타내는 문자열, 오버롤을 나타내는 정수 $A_{i}$, 가격을 나타내는 정수 $B_{i}$, 급여를 나타내는 정수 $C_{i}$, 선수의 이름을 나타내는 문자열이 공백으로 구분되어 주어진다. ($1 \le A_i \le 100;$ $1 \le B_i \le M;$ $1 \le C_i \le 120$)

포지션을 나타내는 문자열은 GK, DF, MF, FW 중 하나이며, 모든 선수의 이름은 영어 알파벳 소문자로만 이루어진 길이 $10$ 이하의 문자열이다.

출력 형식

첫 줄에 팀을 구성할 때 선택한 선수 카드의 오버롤 합의 최댓값을 출력한다. 만약, 팀을 구성하는 방법이 없다면 $-1$을 출력한다.

예제

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
DF 15 4 10 ne
DF 20 5 15 nf
DF 20 6 15 ng
MF 15 2 5 nh
MF 15 2 5 ni
MF 20 3 10 nj
MF 20 4 15 nk
MF 20 5 15 nl
MF 20 6 20 nl
FW 20 10 20 nm
FW 30 15 30 nm

200

예제 설명

주어진 입력 예제는 문제 본문에서 설명한 것과 같다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설