시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 35 32 47.059%

문제

상근이는 술을 먹던 도중 프로그래밍을 못하는 이유를 갑자기 깨달았다. 그 이유는 바로 상근이의 컴퓨터 성능이 좋지 않았기 때문이다. 상근이는 컴퓨터를 사기로 결심했다.

상근이는 컴퓨터를 조립해서 만들 것이다. 따라서, 각 부품을 모두 따로 구매해서 직접 조립해야 한다. 각각의 부품은 하나씩 구매하면 된다.

컴퓨터의 성능은 가장 안 좋은 부품의 성능과 같다. 따라서, 상근이는 예산을 초과하지 않으면서 가장 안 좋은 부품의 성능을 최대로 하려고 한다.

각 부품의 이름과 종류, 성능이 주어진다. 이 때, 상근이의 예산으로 구매할 수 있는 가장 성능이 좋은 컴퓨터를 구하는 프로그램을 작성하시오.

입력

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

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

다음 n개 줄에는 부품의 정보가 "type name price quality"와 같은 형식으로 주어진다. type은 부품의 종류, name은 그 부품의 이름, price는 가격 (0 ≤ price ≤ 1,000,000), quality는 성능 (0 ≤ quality ≤ 1,000,000,000)이다.

부품의 이름은 겹치지 않고, 성능은 숫자가 높을수록 좋은 것이다. 문자열에는 글자와 숫자, 그리고 밑 줄만을 포함하며, 최대 길이는 20글자이다.

항상 주어진 예산으로 컴퓨터를 조립할 수 있는 경우만 입력으로 주어진다.

출력

각 테스트 케이스에 대해서, 상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터의 성능을 출력한다.

예제 입력 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

예제 출력 1

9

힌트

W3sicHJvYmxlbV9pZCI6IjM2OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjRcdWQ0ZThcdWQxMzAgXHVjODcwXHViOWJkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMjIwXHVjNzQ0IFx1YmEzOVx1YjM1OCBcdWIzYzRcdWM5MTEgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkXHVjNzQ0IFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM3MjBcdWI5N2MgXHVhYzExXHVjNzkwXHVhZTMwIFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWJjMTRcdWI4NWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMxMzFcdWIyYTVcdWM3NzQgXHVjODhiXHVjOWMwIFx1YzU0YVx1YzU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjMGFjXHVhZTMwXHViODVjIFx1YWNiMFx1YzJlY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWM4NzBcdWI5YmRcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjMDEgXHViZDgwXHVkNDg4XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWI1MzBcdWI4NWMgXHVhZDZjXHViOWU0XHVkNTc0XHVjMTFjIFx1YzljMVx1YzgxMSBcdWM4NzBcdWI5YmRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViZDgwXHVkNDg4XHVjNzQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFkNmNcdWI5ZTRcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNlZjRcdWQ0ZThcdWQxMzBcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM1NDggXHVjODhiXHVjNzQwIFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWMxMzFcdWIyYTVcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2MDhcdWMwYjBcdWM3NDQgXHVjZDA4XHVhY2ZjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNTQ4IFx1Yzg4Ylx1Yzc0MCBcdWJkODBcdWQ0ODhcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHViZDgwXHVkNDg4XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1YWNmYyBcdWM4ODVcdWI5NTgsIFx1YzEzMVx1YjJhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM2MDhcdWMwYjBcdWM3M2NcdWI4NWMgXHVhZDZjXHViOWU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzEzMVx1YjJhNVx1Yzc3NCBcdWM4OGJcdWM3NDAgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZDgwXHVkNDg4XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVhY2ZjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM2MDhcdWMwYjAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEsMDAwLCAxICZsZTsgYiAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwICZxdW90O3R5cGUgbmFtZSBwcmljZSBxdWFsaXR5JnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiB0eXBlXHVjNzQwIFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWM4ODVcdWI5NTgsIG5hbWVcdWM3NDAgXHVhZGY4IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWM3NzRcdWI5ODQsIHByaWNlXHViMjk0IFx1YWMwMFx1YWNhOSAoMCAmbGU7IHByaWNlICZsZTsgMSwwMDAsMDAwKSwgcXVhbGl0eVx1YjI5NCBcdWMxMzFcdWIyYTUgKDAgJmxlOyBxdWFsaXR5ICZsZTsgMSwwMDAsMDAwLDAwMClcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWNlMCwgXHVjMTMxXHViMmE1XHVjNzQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWIxOTJcdWM3NDRcdWMyMThcdWI4NWQgXHVjODhiXHVjNzQwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHViMjk0IFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWMyMmJcdWM3OTAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJjMTEgXHVjOTA0XHViOWNjXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YmE3MCwgXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NFx1YjI5NCAyMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YzhmY1x1YzViNFx1YzljNCBcdWM2MDhcdWMwYjBcdWM3M2NcdWI4NWMgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1Yzg3MFx1YjliZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzYwOFx1YzBiMFx1YzczY1x1Yjg1YyBcdWFkNmNcdWI5ZTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWMxMzFcdWIyYTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2OTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBc3NlbWJsZSIsImRlc2NyaXB0aW9uIjoiPHA+UmVjZW50bHkgeW91ciB0ZWFtIG5vdGljZWQgdGhhdCB0aGUgY29tcHV0ZXIgeW91IHVzZSB0byBwcmFjdGljZSBmb3IgcHJvZ3JhbW1pbmcgY29udGVzdHMgaXMgbm90IGdvb2QgZW5vdWdoIGFueW1vcmUuIFRoZXJlZm9yZSwgeW91IGRlY2lkZSB0byBidXkgYSBuZXcgY29tcHV0ZXIuPFwvcD5cclxuXHJcbjxwPlRvIG1ha2UgdGhlIGlkZWFsIGNvbXB1dGVyIGZvciB5b3VyIG5lZWRzLCB5b3UgZGVjaWRlIHRvIGJ1eSBzZXBhcmF0ZSBjb21wb25lbnRzIGFuZCBhc3NlbWJsZSB0aGUgY29tcHV0ZXIgeW91cnNlbGYuIFlvdSBuZWVkIHRvIGJ1eSBleGFjdGx5IG9uZSBvZiBlYWNoIHR5cGUgb2YgY29tcG9uZW50LjxcL3A+XHJcblxyXG48cD5UaGUgcHJvYmxlbSBpcyB3aGljaCBjb21wb25lbnRzIHRvIGJ1eS4gQXMgeW91IGFsbCBrbm93LCB0aGUgcXVhbGl0eSBvZiBhIGNvbXB1dGVyIGlzIGVxdWFsIHRvIHRoZSBxdWFsaXR5IG9mIGl0cyB3ZWFrZXN0IGNvbXBvbmVudC4gVGhlcmVmb3JlLCB5b3Ugd2FudCB0byBtYXhpbWl6ZSB0aGUgcXVhbGl0eSBvZiB0aGUgY29tcG9uZW50IHdpdGggdGhlIGxvd2VzdCBxdWFsaXR5LCB3aGlsZSBub3QgZXhjZWVkaW5nIHlvdXIgYnVkZ2V0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VyczogMSAmbGU7IG4gJmxlOyAxIDAwMCwgdGhlIG51bWJlciBvZiBhdmFpbGFibGUgY29tcG9uZW50cyBhbmQgMSAmbGU7IGIgJmxlOyAxIDAwMCAwMDAgMDAwLCB5b3VyIGJ1ZGdldC48XC9saT5cclxuXHQ8bGk+biBsaW5lcyBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdDogJmxkcXVvO3R5cGUgbmFtZSBwcmljZSBxdWFsaXR5JnJkcXVvOywgd2hlcmUgdHlwZSBpcyBhIHN0cmluZyB3aXRoIHRoZSB0eXBlIG9mIHRoZSBjb21wb25lbnQsIG5hbWUgaXMgYSBzdHJpbmcgd2l0aCB0aGUgdW5pcXVlIG5hbWUgb2YgdGhlIGNvbXBvbmVudCwgcHJpY2UgaXMgYW4gaW50ZWdlciAoMCAmbGU7IHByaWNlICZsZTsgMSAwMDAgMDAwKSB3aGljaCByZXByZXNlbnRzIHRoZSBwcmljZSBvZiB0aGUgY29tcG9uZW50IGFuZCBxdWFsaXR5IGlzIGFuIGludGVnZXIgKDAgJmxlOyBxdWFsaXR5ICZsZTsgMSAwMDAgMDAwIDAwMCkgd2hpY2ggcmVwcmVzZW50cyB0aGUgcXVhbGl0eSBvZiB0aGUgY29tcG9uZW50IChoaWdoZXIgaXMgYmV0dGVyKS4gVGhlIHN0cmluZ3MgY29udGFpbiBvbmx5IGxldHRlcnMsIGRpZ2l0cyBhbmQgdW5kZXJzY29yZXMgYW5kIGhhdmUgYSBtYXhpbWFsIGxlbmd0aCBvZiAyMCBjaGFyYWN0ZXJzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkl0IHdpbGwgYWx3YXlzIHBvc3NpYmxlIHRvIGNvbnN0cnVjdCBhIGNvbXB1dGVyIHdpdGggeW91ciBidWRnZXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggb25lIGludGVnZXI6IHRoZSBtYXhpbWFsIHBvc3NpYmxlIHF1YWxpdHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=