시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 77 52 50 69.444%

문제

ACM-ICPC 아시아 지역 대회기간 중 대전의 패스트 푸드 음식점들은 그들의 음식점을 홍보하기 위해 이벤트를 준비한다. 특정 음식을 먹을 때 마다 스티커를 하나 제공하는데 스티커를 모으면 상금으로 교환할 수 있다. 같은 종류의 스티커가 필요한 상금은 여러 번 교환할 수 있으며, 같은 종류의 스티커를 가진 서로 다른 액수의 상금은 존재하지 않는다. 상금 교환에 필요없는 스티커도 있다.

지역대회를 보러 가면서, 당신의 코치가 패스트 푸드 음식점에서만 식사를 하도록 허락했을 때, 얼마나 많은 상금을 획득할 수 있을까?

입력

입력은 여러개의 테스트 케이스로 이루어져있다. 각 테스트 케이스마다 첫째 줄에는 서로 다른 상금의 종류 n (1 ≤ n ≤ 10) 과 코치가 가지고 있는 스티커의 종류 (1 ≤ m ≤ 30, 종류는 1부터 m까지 번호가 매겨진다) 가 주어진다. 다음 n개의 줄은 상금에 관한 정보가 주어지는데 각 줄마다 첫번 째 정수는 해당 상금에 필요한 스티커의 개수 k (1 ≤ k ≤ m) 가 주어지며 뒤이어 k개의 정수에는 해당 상금에 필요한 스티커의 종류가 주어지며 마지막으로 상금의 액수가 주어진다 (최대 1,000,000) . n개의 모든 입력이 주어진 후 마지막 줄은 코치가 가지고 있는 1부터 m까지 스티커의 개수가 각각 주어진다. 각각의 스티커의 개수는 100개 이하이다.

출력

각각의 케이스마다 최대 상금의 액수를 한줄씩 출력한다.

예제 입력 1

3
2 10
3 1 2 3 100
4 4 5 6 7 200
2 3 1 4 5 2 2 1 3 4
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 3 4 5 6
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 0 4 5 6

예제 출력 1

500
2500
1900
W3sicHJvYmxlbV9pZCI6IjkzMjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjhcdWMyYTRcdWQyYjggXHVkNDc4XHViNGRjIFx1YzBjMVx1YWUwOCIsImRlc2NyaXB0aW9uIjoiPHA+QUNNLUlDUEMgXHVjNTQ0XHVjMmRjXHVjNTQ0IFx1YzljMFx1YzVlZCBcdWIzMDBcdWQ2OGNcdWFlMzBcdWFjMDQmbmJzcDtcdWM5MTEgXHViMzAwXHVjODA0XHVjNzU4IFx1ZDMyOFx1YzJhNFx1ZDJiOCBcdWQ0NzhcdWI0ZGMgXHVjNzRjXHVjMmRkXHVjODEwXHViNGU0XHVjNzQwIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NDQgXHVkNjRkXHViY2Y0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM3NzRcdWJjYTRcdWQyYjhcdWI5N2MgXHVjOTAwXHViZTQ0XHVkNTVjXHViMmU0LiBcdWQyYjlcdWM4MTUgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YmEzOVx1Yzc0NCZuYnNwO1x1YjU0YyBcdWI5YzhcdWIyZTQgXHVjMmE0XHVkMmYwXHVjZWU0XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjZjVcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMmE0XHVkMmYwXHVjZWU0XHViOTdjIFx1YmFhOFx1YzczY1x1YmE3NCBcdWMwYzFcdWFlMDhcdWM3M2NcdWI4NWMgXHVhZDUwXHVkNjU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjMmE0XHVkMmYwXHVjZWU0XHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMwYzFcdWFlMDhcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWFkNTBcdWQ2NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyYTRcdWQyZjBcdWNlZTRcdWI5N2MgXHVhYzAwXHVjOWM0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNTYxXHVjMjE4XHVjNzU4IFx1YzBjMVx1YWUwOFx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMwYzFcdWFlMDggXHVhZDUwXHVkNjU4XHVjNWQwIFx1ZDU0NFx1YzY5NFx1YzVjNlx1YjI5NCBcdWMyYTRcdWQyZjBcdWNlZTRcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWM1ZWRcdWIzMDBcdWQ2OGNcdWI5N2MgXHViY2Y0XHViN2VjIFx1YWMwMFx1YmE3NFx1YzExYywgXHViMmY5XHVjMmUwXHVjNzU4IFx1Y2Y1NFx1Y2U1OFx1YWMwMCBcdWQzMjhcdWMyYTRcdWQyYjggXHVkNDc4XHViNGRjJm5ic3A7XHVjNzRjXHVjMmRkXHVjODEwXHVjNWQwXHVjMTFjXHViOWNjIFx1YzJkZFx1YzBhY1x1Yjk3YyBcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNWM4XHViNzdkXHVkNTg4XHVjNzQ0IFx1YjU0YywmbmJzcDtcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzQwJm5ic3A7XHVjMGMxXHVhZTA4XHVjNzQ0IFx1ZDY4ZFx1YjRkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzBjMVx1YWUwOFx1Yzc1OCBcdWM4ODVcdWI5NTggbiAoMSAmbGU7IG4gJmxlOyAxMCkgXHVhY2ZjIFx1Y2Y1NFx1Y2U1OFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWM4ODVcdWI5NTggKDEgJmxlOyBtICZsZTsgMzAsIFx1Yzg4NVx1Yjk1OFx1YjI5NCAxXHViZDgwXHVkMTMwIG1cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzljNFx1YjJlNCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1YzBjMVx1YWUwOFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1Y2NhYlx1YmM4OCBcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IFx1ZDU3NFx1YjJmOSBcdWMwYzFcdWFlMDhcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWFjMWNcdWMyMTggayAoMSAmbGU7IGsgJmxlOyBtKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YjRhNFx1Yzc3NFx1YzViNCBrXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YzVkMFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHVjMGMxXHVhZTA4XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyYTRcdWQyZjBcdWNlZTRcdWM3NTggXHVjODg1XHViOTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjMGMxXHVhZTA4XHVjNzU4IFx1YzU2MVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKFx1Y2Q1Y1x1YjMwMCZuYnNwOzEsMDAwLDAwMCkgLiBuXHVhYzFjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDZjNCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIFx1Y2Y1NFx1Y2U1OFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IDFcdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCZuYnNwO1x1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAxXHVhYzAxIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMTAwXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2Q1Y1x1YjMwMCBcdWMwYzFcdWFlMDhcdWM3NTggXHVjNTYxXHVjMjE4XHViOTdjIFx1ZDU1Y1x1YzkwNFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhc3QgRm9vZCBQcml6ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFyb3VuZCByZWdpb25hbCBjb250ZXN0IHRpbWUsIHRoZSBDYW5hZGlhbiBicmFuY2ggb2YgYSBwb3B1bGFyIGZhc3QgZm9vZCByZXN0YXVyYW50IHVzdWFsbHkgcnVucyBhIGdhbWUgdG8gcHJvbW90ZSBpdHMgYnVzaW5lc3MuIENlcnRhaW4gZm9vZCBpdGVtcyBwcm92aWRlIHN0aWNrZXJzLCBhbmQgY2VydGFpbiBjb2xsZWN0aW9uIG9mIGRpZmZlcmVudCBzdGlja2VycyBjYW4gYmUgY29udmVydGVkIHRvIGNhc2ggcHJpemVzLiBJZiBhIHByaXplIHJlcXVpcmVzIHN0aWNrZXIgdHlwZXMgVDxzdWI+MTxcL3N1Yj4sIFQ8c3ViPjI8XC9zdWI+LCAuLi4gLCBUPHN1Yj5rPFwvc3ViPiwgdGhlbiB5b3UgY2FuIGNsYWltIHRoZSBwcml6ZSBpZiB5b3UgaGF2ZSAxIHN0aWNrZXIgb2YgZWFjaCB0eXBlIFQ8c3ViPjE8XC9zdWI+LCBUPHN1Yj4yPFwvc3ViPiwgLi4uICwgVDxzdWI+azxcL3N1Yj4uIEVhY2ggc3RpY2tlciBjYW4gb25seSBiZSB1c2VkIHRvIGNsYWltIG9uZSBwcml6ZS4gSG93ZXZlciwgeW91IG1heSBjbGFpbSBhIHByaXplIG11bHRpcGxlIHRpbWVzIGlmIHlvdSBoYXZlIG11bHRpcGxlIHN0aWNrZXJzIG9mIHRoZSBzYW1lIHR5cGUuIE5vIHR3byBwcml6ZXMgd2lsbCByZXF1aXJlIHRoZSBzYW1lIHR5cGUgb2Ygc3RpY2tlcnMuIFRoZXJlIG1heSBiZSBzb21lIHN0aWNrZXJzIHRoYXQgY2Fubm90IGJlIHVzZWQgdG8gY2xhaW0gYSBjYXNoIHByaXplIChlLmcuIGEgc3RpY2tlciBmb3IgYSBmcmVlIG1pbGtzaGFrZSkuPFwvcD5cclxuXHJcbjxwPk9uIHlvdXIgcm9hZCB0cmlwIHRvIHRoZSByZWdpb25hbCBjb250ZXN0LCB5b3VyIGNvYWNoIGZvcmNlZCB5b3UgdG8gZWF0IGF0IHRoaXMgcmVzdGF1cmFudCBhbmQgY29sbGVjdGVkIGFsbCB0aGUgc3RpY2tlcnMgdG9nZXRoZXIuIEhvdyBtdWNoIGNhc2ggY2FuIHlvdXIgY29hY2ggY2xhaW0/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgc2luZ2xlIGludGVnZXIsIG5vdCBtb3JlIHRoYW4gMTAwMCwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIG4gKDEgJmxlOyBuICZsZTsgMTApIGFuZCBtICgxICZsZTsgbSAmbGU7IDMwKSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB0eXBlcyBvZiBwcml6ZXMsIGFuZCBtIGlzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHR5cGVzIG9mIHN0aWNrZXJzICh0aGUgdHlwZXMgYXJlIGxhYmVsbGVkIDEsIDIsIC4uLiAsIG0pLiBUaGUgbmV4dCBuIGxpbmVzIHNwZWNpZnkgdGhlIHByaXplcy4gRWFjaCBvZiB0aGVzZSBsaW5lcyBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIGsgKDEgJmxlOyBrICZsZTsgbSkgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIHN0aWNrZXIgdHlwZXMgcmVxdWlyZWQgdG8gY2xhaW0gdGhlIHByaXplLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IGsgaW50ZWdlcnMgc3BlY2lmeWluZyB0aGUgdHlwZXMgb2YgdGhlIHN0aWNrZXJzIHJlcXVpcmVkLiBUaGUgXHVmYjAxbmFsIGludGVnZXIgb24gZWFjaCBsaW5lIGlzIHRoZSAocG9zaXRpdmUpIGNhc2ggdmFsdWUgb2YgdGhlIHByaXplIChhdCBtb3N0IDEsMDAwLDAwMCkuIFRoZSBsYXN0IGxpbmUgb2YgZWFjaCBjYXNlIGdpdmVzIG0gbm9ubmVnYXRpdmUgaW50ZWdlcnMsIHdpdGggdGhlIGl0aCBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIHN0aWNrZXJzIG9mIHR5cGUgaSB5b3VyIGNvYWNoIGhhcyBjb2xsZWN0ZWQuIFRoZXJlIGFyZSBubyBtb3JlIHRoYW4gMTAwIHN0aWNrZXJzIG9mIGVhY2ggdHlwZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBkaXNwbGF5IG9uIGEgc2luZ2xlIGxpbmUgdGhlIHRvdGFsIHZhbHVlIG9mIHRoZSBjYXNoIHByaXplcyB0aGF0IGNhbiBiZSBjbGFpbWVkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > North America > Rocky Mountain Regional > 2013 Rocky Mountain Regional Contest A번