컴퓨터 조립

시간 제한1초메모리 제한128 MB

요약

예산 안에서 각 부품 종류별로 하나씩 골라 선택된 부품들의 최소 성능을 최대화하는 값을 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

상근이는 새 컴퓨터를 직접 조립하기로 했다. 컴퓨터를 완성하려면 입력에 등장하는 각 종류(type)의 부품을 종류마다 정확히 하나씩 구매해야 한다.

컴퓨터 전체의 성능은 사용한 부품 중 성능이 가장 낮은 부품의 성능과 같다. 상근이는 주어진 예산을 초과하지 않으면서, 이 "가장 낮은 부품의 성능"을 최대로 만들고 싶다.

각 부품의 종류, 이름, 가격, 성능이 주어질 때, 예산 안에서 조립할 수 있는 컴퓨터의 최대 성능을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 부품의 개수 $n$ 과 예산 $b$ 가 주어진다. ( $1 \le n \le 1{,}000$ , $1 \le b \le 1{,}000{,}000{,}000$ )

다음 $n$ 개의 줄에는 부품 정보가 type name price quality 형식으로 주어진다. type은 부품의 종류, name은 부품의 이름, price는 가격( $0 \le price \le 1{,}000{,}000$ ), quality는 성능( $0 \le quality \le 1{,}000{,}000{,}000$ )이다.

부품의 이름은 서로 겹치지 않으며, 성능은 값이 클수록 좋다. 모든 문자열은 영문자, 숫자, 밑줄(_)로만 이루어지고 길이는 최대 20글자이다.

컴퓨터를 조립하려면 입력에 등장하는 모든 종류에 대해 부품을 종류마다 하나씩 골라야 한다. 입력은 항상 주어진 예산으로 컴퓨터를 조립할 수 있는 경우만 주어진다.

출력

각 테스트 케이스마다, 예산으로 조립할 수 있는 컴퓨터의 최대 성능을 한 줄에 하나씩 출력한다.

예제4

예제 1

입력

1
18 800
processor 3500_MHz 66 5
processor 4200_MHz 103 7
processor 5000_MHz 156 9
processor 6000_MHz 219 12
memory 1_GB 35 3
memory 2_GB 88 6
memory 4_GB 170 12
mainbord all_onboard 52 10
harddisk 250_GB 54 10
harddisk 500_FB 99 12
casing midi 36 10
monitor 17_inch 157 5
monitor 19_inch 175 7
monitor 20_inch 210 9
monitor 22_inch 293 12
mouse cordless_optical 18 12
mouse microsoft 30 9
keyboard office 4 10

예상 출력

예제 2
입력
```
1
1 100
cpu a 50 7
```
예상 출력
```
7
```

예제 3

입력

1
4 10
cpu fast 8 10
cpu slow 3 4
gpu fast 8 10
gpu slow 3 4

예상 출력

예제 4

입력

2
1 100
cpu a 50 7
2 5
cpu a 3 9
cpu b 4 12

예상 출력

7
12