시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 63 45 44 73.333%

문제

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+QUNNLUlDUEMgXHVjNTQ0XHVjMmRjXHVjNTQ0IFx1YzljMFx1YzVlZCBcdWIzMDBcdWQ2OGNcdWFlMzBcdWFjMDQmbmJzcDtcdWM5MTEgXHViMzAwXHVjODA0XHVjNzU4IFx1ZDMyOFx1YzJhNFx1ZDJiOCBcdWQ0NzhcdWI0ZGMgXHVjNzRjXHVjMmRkXHVjODEwXHViNGU0XHVjNzQwIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NDQgXHVkNjRkXHViY2Y0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM3NzRcdWJjYTRcdWQyYjhcdWI5N2MgXHVjOTAwXHViZTQ0XHVkNTVjXHViMmU0LiBcdWQyYjlcdWM4MTUgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YmEzOVx1Yzc0NCZuYnNwO1x1YjU0YyBcdWI5YzhcdWIyZTQgXHVjMmE0XHVkMmYwXHVjZWU0XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjZjVcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMmE0XHVkMmYwXHVjZWU0XHViOTdjIFx1YmFhOFx1YzczY1x1YmE3NCBcdWMwYzFcdWFlMDhcdWM3M2NcdWI4NWMgXHVhZDUwXHVkNjU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjMmE0XHVkMmYwXHVjZWU0XHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMwYzFcdWFlMDhcdWM3NDAgXHVjNWVjXHViN2VjXHViYzg4IFx1YWQ1MFx1ZDY1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yjk3YyBcdWFjMDBcdWM5YzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM1NjFcdWMyMThcdWM3NTggXHVjMGMxXHVhZTA4XHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzBjMVx1YWUwOCBcdWFkNTBcdWQ2NThcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVjNWM2XHViMjk0IFx1YzJhNFx1ZDJmMFx1Y2VlNFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzVlZFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWJjZjRcdWI3ZWMgXHVhYzAwXHViYTc0XHVjMTFjLCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjZjU0XHVjZTU4XHVhYzAwIFx1ZDMyOFx1YzJhNFx1ZDJiOCBcdWQ0NzhcdWI0ZGMmbmJzcDtcdWM3NGNcdWMyZGRcdWM4MTBcdWM1ZDBcdWMxMWNcdWI5Y2MgXHVjMmRkXHVjMGFjXHViOTdjIFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1YzhcdWI3N2RcdWQ1ODhcdWM3NDQgXHViNTRjLCZuYnNwO1x1YzViY1x1YjljOFx1YjA5OCBcdWI5Y2VcdWM3NDAmbmJzcDtcdWMwYzFcdWFlMDhcdWM3NDQgXHVkNjhkXHViNGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMGMxXHVhZTA4XHVjNzU4IFx1Yzg4NVx1Yjk1OCBuICgxICZsZTsgbiAmbGU7IDEwKSBcdWFjZmMgXHVjZjU0XHVjZTU4XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1Yzg4NVx1Yjk1OCAoMSAmbGU7IG0gJmxlOyAzMCwgXHVjODg1XHViOTU4XHViMjk0IDFcdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0XHViMmU0KSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVjMGMxXHVhZTA4XHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjY2FiXHViYzg4IFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVkNTc0XHViMmY5IFx1YzBjMVx1YWUwOFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1YWMxY1x1YzIxOCBrICgxICZsZTsgayAmbGU7IG0pIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHViNGE0XHVjNzc0XHVjNWI0IGtcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVjNWQwXHViMjk0IFx1ZDU3NFx1YjJmOSBcdWMwYzFcdWFlMDhcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJhNFx1ZDJmMFx1Y2VlNFx1Yzc1OCBcdWM4ODVcdWI5NThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWMwYzFcdWFlMDhcdWM3NTggXHVjNTYxXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoXHVjZDVjXHViMzAwJm5ic3A7MSwwMDAsMDAwKSAuIG5cdWFjMWNcdWM3NTggXHViYWE4XHViNGUwIFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNmM0IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHVjZjU0XHVjZTU4XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBtXHVhZTRjXHVjOWMwJm5ic3A7XHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDFcdWFjMDEgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMmE0XHVkMmYwXHVjZWU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxMDBcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjZDVjXHViMzAwIFx1YzBjMVx1YWUwOFx1Yzc1OCBcdWM1NjFcdWMyMThcdWI5N2MgXHVkNTVjXHVjOTA0XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzI5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFzdCBGb29kIFByaXplcyIsImRlc2NyaXB0aW9uIjoiPHA+QXJvdW5kIHJlZ2lvbmFsIGNvbnRlc3QgdGltZSwgdGhlIENhbmFkaWFuIGJyYW5jaCBvZiBhIHBvcHVsYXIgZmFzdCBmb29kIHJlc3RhdXJhbnQgdXN1YWxseSBydW5zIGEgZ2FtZSB0byBwcm9tb3RlIGl0cyBidXNpbmVzcy4gQ2VydGFpbiBmb29kIGl0ZW1zIHByb3ZpZGUgc3RpY2tlcnMsIGFuZCBjZXJ0YWluIGNvbGxlY3Rpb24gb2YgZGlmZmVyZW50IHN0aWNrZXJzIGNhbiBiZSBjb252ZXJ0ZWQgdG8gY2FzaCBwcml6ZXMuIElmIGEgcHJpemUgcmVxdWlyZXMgc3RpY2tlciB0eXBlcyBUPHN1Yj4xPFwvc3ViPiwgVDxzdWI+MjxcL3N1Yj4sIC4uLiAsIFQ8c3ViPms8XC9zdWI+LCB0aGVuIHlvdSBjYW4gY2xhaW0gdGhlIHByaXplIGlmIHlvdSBoYXZlIDEgc3RpY2tlciBvZiBlYWNoIHR5cGUgVDxzdWI+MTxcL3N1Yj4sIFQ8c3ViPjI8XC9zdWI+LCAuLi4gLCBUPHN1Yj5rPFwvc3ViPi4gRWFjaCBzdGlja2VyIGNhbiBvbmx5IGJlIHVzZWQgdG8gY2xhaW0gb25lIHByaXplLiBIb3dldmVyLCB5b3UgbWF5IGNsYWltIGEgcHJpemUgbXVsdGlwbGUgdGltZXMgaWYgeW91IGhhdmUgbXVsdGlwbGUgc3RpY2tlcnMgb2YgdGhlIHNhbWUgdHlwZS4gTm8gdHdvIHByaXplcyB3aWxsIHJlcXVpcmUgdGhlIHNhbWUgdHlwZSBvZiBzdGlja2Vycy4gVGhlcmUgbWF5IGJlIHNvbWUgc3RpY2tlcnMgdGhhdCBjYW5ub3QgYmUgdXNlZCB0byBjbGFpbSBhIGNhc2ggcHJpemUgKGUuZy4gYSBzdGlja2VyIGZvciBhIGZyZWUgbWlsa3NoYWtlKS48XC9wPlxyXG5cclxuPHA+T24geW91ciByb2FkIHRyaXAgdG8gdGhlIHJlZ2lvbmFsIGNvbnRlc3QsIHlvdXIgY29hY2ggZm9yY2VkIHlvdSB0byBlYXQgYXQgdGhpcyByZXN0YXVyYW50IGFuZCBjb2xsZWN0ZWQgYWxsIHRoZSBzdGlja2VycyB0b2dldGhlci4gSG93IG11Y2ggY2FzaCBjYW4geW91ciBjb2FjaCBjbGFpbT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBzaW5nbGUgaW50ZWdlciwgbm90IG1vcmUgdGhhbiAxMDAwLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAxMCkgYW5kIG0gKDEgJmxlOyBtICZsZTsgMzApLCB3aGVyZSBuIGlzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHR5cGVzIG9mIHByaXplcywgYW5kIG0gaXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgdHlwZXMgb2Ygc3RpY2tlcnMgKHRoZSB0eXBlcyBhcmUgbGFiZWxsZWQgMSwgMiwgLi4uICwgbSkuIFRoZSBuZXh0IG4gbGluZXMgc3BlY2lmeSB0aGUgcHJpemVzLiBFYWNoIG9mIHRoZXNlIGxpbmVzIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgayAoMSAmbGU7IGsgJmxlOyBtKSBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2Ygc3RpY2tlciB0eXBlcyByZXF1aXJlZCB0byBjbGFpbSB0aGUgcHJpemUuIFRoaXMgaXMgZm9sbG93ZWQgYnkgayBpbnRlZ2VycyBzcGVjaWZ5aW5nIHRoZSB0eXBlcyBvZiB0aGUgc3RpY2tlcnMgcmVxdWlyZWQuIFRoZSBcdWZiMDFuYWwgaW50ZWdlciBvbiBlYWNoIGxpbmUgaXMgdGhlIChwb3NpdGl2ZSkgY2FzaCB2YWx1ZSBvZiB0aGUgcHJpemUgKGF0IG1vc3QgMSwwMDAsMDAwKS4gVGhlIGxhc3QgbGluZSBvZiBlYWNoIGNhc2UgZ2l2ZXMgbSBub25uZWdhdGl2ZSBpbnRlZ2Vycywgd2l0aCB0aGUgaXRoIGludGVnZXIgZ2l2aW5nIHRoZSBudW1iZXIgb2Ygc3RpY2tlcnMgb2YgdHlwZSBpIHlvdXIgY29hY2ggaGFzIGNvbGxlY3RlZC4gVGhlcmUgYXJlIG5vIG1vcmUgdGhhbiAxMDAgc3RpY2tlcnMgb2YgZWFjaCB0eXBlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIGRpc3BsYXkgb24gYSBzaW5nbGUgbGluZSB0aGUgdG90YWwgdmFsdWUgb2YgdGhlIGNhc2ggcHJpemVzIHRoYXQgY2FuIGJlIGNsYWltZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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