Assembling a Computer

Time limit1sMemory limit128 MB

Summary

Choose one part per category within a budget to maximize the minimum quality among chosen parts, typically via binary search plus greedy cheapest-part selection.

Level: Medium6 of 10
Topics: Binary search, Greedy, Implementation
Solved: No attempts yet

Problem

Sang-geun decided to build a new computer himself. To complete it, he must buy exactly one part of every type that appears in the input.

The overall performance of the computer equals the performance of its worst part (the one with the lowest performance). Without exceeding a given budget, Sang-geun wants to maximize this "performance of the worst part".

Given the type, name, price, and performance of every available part, write a program that computes the maximum performance of a computer he can assemble within the budget.

Input

The first line contains the number of test cases, which is at most 100.

The first line of each test case contains the number of parts $n$ and the budget $b$ . ( $1 \le n \le 1{,}000$ , $1 \le b \le 1{,}000{,}000{,}000$ )

Each of the next $n$ lines describes one part in the format type name price quality, where type is the part's category, name is its name, price is its cost ( $0 \le price \le 1{,}000{,}000$ ), and quality is its performance ( $0 \le quality \le 1{,}000{,}000{,}000$ ).

All part names are distinct, and a larger quality value means better performance. Every string consists only of letters, digits, and underscores (_) and has length at most 20.

To assemble a computer, exactly one part must be chosen for every type that appears in the input. Every input is guaranteed to allow assembling a computer within the given budget.

Output

For each test case, print on its own line the maximum performance of a computer that can be assembled within the budget.

Examples4

Example 1

Input

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

Expected output

Example 2
Input
```
1
1 100
cpu a 50 7
```
Expected output
```
7
```

Example 3

Input

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

Expected output

Example 4

Input

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

Expected output

7
12