시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 77 37 34 48.571%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 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+XHJcblxyXG48cD5cdWFjMDEgXHViZDgwXHVkNDg4XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1YWNmYyBcdWM4ODVcdWI5NTgsIFx1YzEzMVx1YjJhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzYwOFx1YzBiMFx1YzczY1x1Yjg1YyBcdWFkNmNcdWI5ZTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjMTMxXHViMmE1XHVjNzc0IFx1Yzg4Ylx1Yzc0MCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAxMDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzYwOFx1YzBiMCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMSwwMDAsIDEgJmxlOyBiICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgJnF1b3Q7dHlwZSBuYW1lIHByaWNlIHF1YWxpdHkmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHR5cGVcdWM3NDAgXHViZDgwXHVkNDg4XHVjNzU4IFx1Yzg4NVx1Yjk1OCwgbmFtZVx1Yzc0MCBcdWFkZjggXHViZDgwXHVkNDg4XHVjNzU4IFx1Yzc3NFx1Yjk4NCwgcHJpY2VcdWIyOTQgXHVhYzAwXHVhY2E5ICgwICZsZTsgcHJpY2UgJmxlOyAxLDAwMCwwMDApLCBxdWFsaXR5XHViMjk0IFx1YzEzMVx1YjJhNSAoMCAmbGU7IHF1YWxpdHkgJmxlOyAxLDAwMCwwMDAsMDAwKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDgwXHVkNDg4XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWMxMzFcdWIyYTVcdWM3NDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjE5Mlx1Yzc0NFx1YzIxOFx1Yjg1ZCBcdWM4OGJcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWIyOTQgXHVhZTAwXHVjNzkwXHVjNjQwIFx1YzIyYlx1Yzc5MCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YmMxMSBcdWM5MDRcdWI5Y2NcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViYTcwLCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHViMjk0IDIwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzYwOFx1YzBiMFx1YzczY1x1Yjg1YyBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjODcwXHViOWJkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNjA4XHVjMGIwXHVjNzNjXHViODVjIFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNzU4IFx1YzEzMVx1YjJhNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY5MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFzc2VtYmxlIiwiZGVzY3JpcHRpb24iOiI8cD5SZWNlbnRseSB5b3VyIHRlYW0gbm90aWNlZCB0aGF0IHRoZSBjb21wdXRlciB5b3UgdXNlIHRvIHByYWN0aWNlIGZvciBwcm9ncmFtbWluZyBjb250ZXN0cyBpcyBub3QgZ29vZCBlbm91Z2ggYW55bW9yZS4gVGhlcmVmb3JlLCB5b3UgZGVjaWRlIHRvIGJ1eSBhIG5ldyBjb21wdXRlci48XC9wPlxyXG5cclxuPHA+VG8gbWFrZSB0aGUgaWRlYWwgY29tcHV0ZXIgZm9yIHlvdXIgbmVlZHMsIHlvdSBkZWNpZGUgdG8gYnV5IHNlcGFyYXRlIGNvbXBvbmVudHMgYW5kIGFzc2VtYmxlIHRoZSBjb21wdXRlciB5b3Vyc2VsZi4gWW91IG5lZWQgdG8gYnV5IGV4YWN0bHkgb25lIG9mIGVhY2ggdHlwZSBvZiBjb21wb25lbnQuPFwvcD5cclxuXHJcbjxwPlRoZSBwcm9ibGVtIGlzIHdoaWNoIGNvbXBvbmVudHMgdG8gYnV5LiBBcyB5b3UgYWxsIGtub3csIHRoZSBxdWFsaXR5IG9mIGEgY29tcHV0ZXIgaXMgZXF1YWwgdG8gdGhlIHF1YWxpdHkgb2YgaXRzIHdlYWtlc3QgY29tcG9uZW50LiBUaGVyZWZvcmUsIHlvdSB3YW50IHRvIG1heGltaXplIHRoZSBxdWFsaXR5IG9mIHRoZSBjb21wb25lbnQgd2l0aCB0aGUgbG93ZXN0IHF1YWxpdHksIHdoaWxlIG5vdCBleGNlZWRpbmcgeW91ciBidWRnZXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzOiAxICZsZTsgbiAmbGU7IDEgMDAwLCB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBjb21wb25lbnRzIGFuZCAxICZsZTsgYiAmbGU7IDEgMDAwIDAwMCAwMDAsIHlvdXIgYnVkZ2V0LjxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0OiAmbGRxdW87dHlwZSBuYW1lIHByaWNlIHF1YWxpdHkmcmRxdW87LCB3aGVyZSB0eXBlIGlzIGEgc3RyaW5nIHdpdGggdGhlIHR5cGUgb2YgdGhlIGNvbXBvbmVudCwgbmFtZSBpcyBhIHN0cmluZyB3aXRoIHRoZSB1bmlxdWUgbmFtZSBvZiB0aGUgY29tcG9uZW50LCBwcmljZSBpcyBhbiBpbnRlZ2VyICgwICZsZTsgcHJpY2UgJmxlOyAxIDAwMCAwMDApIHdoaWNoIHJlcHJlc2VudHMgdGhlIHByaWNlIG9mIHRoZSBjb21wb25lbnQgYW5kIHF1YWxpdHkgaXMgYW4gaW50ZWdlciAoMCAmbGU7IHF1YWxpdHkgJmxlOyAxIDAwMCAwMDAgMDAwKSB3aGljaCByZXByZXNlbnRzIHRoZSBxdWFsaXR5IG9mIHRoZSBjb21wb25lbnQgKGhpZ2hlciBpcyBiZXR0ZXIpLiBUaGUgc3RyaW5ncyBjb250YWluIG9ubHkgbGV0dGVycywgZGlnaXRzIGFuZCB1bmRlcnNjb3JlcyBhbmQgaGF2ZSBhIG1heGltYWwgbGVuZ3RoIG9mIDIwIGNoYXJhY3RlcnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgd2lsbCBhbHdheXMgcG9zc2libGUgdG8gY29uc3RydWN0IGEgY29tcHV0ZXIgd2l0aCB5b3VyIGJ1ZGdldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBvbmUgaW50ZWdlcjogdGhlIG1heGltYWwgcG9zc2libGUgcXVhbGl0eS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==