시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 304 127 96 49.231%

문제

종혁이는 자물쇠로 잠긴 M개의 돼지우리가 있는 농장에서 일하고 있다. 종혁이는 열쇠가 없기 때문에 우리들을 열지 못한다.

이 농장에 손님들은 하루에 한명씩 방문한다. 이들은 몇몇 우리 열쇠를 가지고 있고, 이 우리들을 연 다음 자신이 원하는 만큼의 돼지를 사간다.

농장 운영 방식은 아래와 같다.

  1. 손님이 도착해서 가지고 있는 열쇠로 열 수 있는 모든 우리들을 연다.
  2. 손님에게 몇몇 돼지들을 판다. (손님이 원하는 만큼을 초과하여 돼지를 팔 순 없지만 그 이하로는 팔 수 있다.)
  3. 종혁이는 팔고 남은 돼지들을 현재 열려져 있는 우리들을 상대로 재분배 할 수 있다.

문제는 우리에 들어갈 수 있는 돼지 숫자의 제한이 없다고 할 때 손님들이 방문한 동안 종혁이가 최대로 팔 수 있는 총 돼지의 숫자를 구하는 것이다.

입력

첫째 줄에 돼지 우리 숫자를 나타내는 M(1≤M≤1,000)과 손님들의 숫자를 나타내는 N(1≤N≤100)이 공백으로 구분되어 주어진다. 돼지우리는 1번부터 M번까지의 숫자로 매겨져 있고 손님 역시 1번부터 N번의 숫자로 매겨져 있다.

두 번째 줄에는 각각의 돼지우리에 있는 초기 돼지 숫자를 나타내는 M개의 수가 공백으로 구분되어 주어진다. 이 수는 0 이상 1,000 이하의 수이다.

그 다음 N개의 줄에는 N명의 손님들에 대한 정보가 주어진다. i+2번째 줄에는 i번째 손님에 대한 정보 A, K1, K2, …, KA, B가 주어지는데 이는 i번째 손님이 K1, K2, …, KA번째 우리 열쇠를 가지고 있고 B마리의 돼지를 사길 원한다는 의미이다. A와 B는 0 이상의 정수이다.

출력

첫째 줄에 최대 팔 수 있는 돼지 숫자를 출력한다.

예제 입력 1

3 3
3 1 10
2 1 2 2 
2 1 3 3
1 2 6

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjE2NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZmNcdWM5YzAgXHVjN2ExXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4ODVcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzkwXHViYjNjXHVjMWUwXHViODVjIFx1YzdhMFx1YWUzNCBNXHVhYzFjXHVjNzU4IFx1YjNmY1x1YzljMFx1YzZiMFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHViMThkXHVjN2E1XHVjNWQwXHVjMTFjIFx1Yzc3Y1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM1ZjRcdWMxZTBcdWFjMDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM2YjBcdWI5YWNcdWI0ZTRcdWM3NDQgXHVjNWY0XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNWQwIFx1ZDU1Y1x1YmE4NVx1YzUyOSBcdWJjMjlcdWJiMzhcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWJhODdcdWJhODcgXHVjNmIwXHViOWFjIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjNmIwXHViOWFjXHViNGU0XHVjNzQ0IFx1YzVmMCBcdWIyZTRcdWM3NGMgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2NcdWM3NTggXHViM2ZjXHVjOWMwXHViOTdjIFx1YzBhY1x1YWMwNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMThkXHVjN2E1IFx1YzZiNFx1YzYwMSBcdWJjMjlcdWMyZGRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWMxOTBcdWIyZDhcdWM3NzQgXHViM2M0XHVjYzI5XHVkNTc0XHVjMTFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjMWUwXHViODVjIFx1YzVmNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM2YjBcdWI5YWNcdWI0ZTRcdWM3NDQgXHVjNWYwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxOTBcdWIyZDhcdWM1ZDBcdWFjOGMgXHViYTg3XHViYTg3IFx1YjNmY1x1YzljMFx1YjRlNFx1Yzc0NCBcdWQzMTBcdWIyZTQuIChcdWMxOTBcdWIyZDhcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3Y1x1Yzc0NCZuYnNwOzxzdHJvbmc+XHVjZDA4XHVhY2ZjPFwvc3Ryb25nPlx1ZDU1OFx1YzVlYyBcdWIzZmNcdWM5YzBcdWI5N2MgXHVkMzE0IFx1YzIxYyBcdWM1YzZcdWM5YzBcdWI5Y2MgXHVhZGY4IFx1Yzc3NFx1ZDU1OFx1Yjg1Y1x1YjI5NCBcdWQzMTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvbGk+XHJcblx0PGxpPlx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQzMTRcdWFjZTAgXHViMGE4XHVjNzQwIFx1YjNmY1x1YzljMFx1YjRlNFx1Yzc0NCBcdWQ2MDRcdWM3YWMgXHVjNWY0XHViODI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM2YjBcdWI5YWNcdWI0ZTRcdWM3NDQgXHVjMGMxXHViMzAwXHViODVjIFx1YzdhY1x1YmQ4NFx1YmMzMCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjNmIwXHViOWFjXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNmY1x1YzljMCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjODFjXHVkNTVjXHVjNzc0IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YzE5MFx1YjJkOFx1YjRlNFx1Yzc3NCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHViM2Q5XHVjNTQ4IFx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkMzE0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDFkIFx1YjNmY1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2ZjXHVjOWMwIFx1YzZiMFx1YjlhYyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE0oMSZsZTtNJmxlOzEsMDAwKVx1YWNmYyBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIzZmNcdWM5YzBcdWM2YjBcdWI5YWNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBNXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHVhY2UwIFx1YzE5MFx1YjJkOCBcdWM1ZWRcdWMyZGMgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2ZjXHVjOWMwXHVjNmIwXHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNkMDhcdWFlMzAgXHViM2ZjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgMCBcdWM3NzRcdWMwYzEgMSwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHViYTg1XHVjNzU4IFx1YzE5MFx1YjJkOFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaSsyXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzE5MFx1YjJkOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0IEEsIEsxLCBLMiwgJmhlbGxpcDssIEtBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWM3NzRcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWMxOTBcdWIyZDhcdWM3NzQgSzEsIEsyLCAmaGVsbGlwOywgS0FcdWJjODhcdWM5ZjggXHVjNmIwXHViOWFjIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwIEJcdWI5YzhcdWI5YWNcdWM3NTggXHViM2ZjXHVjOWMwXHViOTdjIFx1YzBhY1x1YWUzOCBcdWM2ZDBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBBXHVjNjQwIEJcdWIyOTQgMCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1ZDMxNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNmY1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE2NTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQSUdTIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyB3b3JrcyBvbiBhIHBpZyBmYXJtIHRoYXQgY29uc2lzdHMgb2YgTSBsb2NrZWQgcGlnLWhvdXNlcyBhbmQgTWlya28gY2FuJiMzOTt0IHVubG9jayBhbnkgcGlnaG91c2UgYmVjYXVzZSBoZSBkb2VzbiYjMzk7dCBoYXZlIHRoZSBrZXlzLiBDdXN0b21lcnMgY29tZSB0byB0aGUgZmFybSBvbmUgYWZ0ZXIgYW5vdGhlci4gRWFjaCBvZiB0aGVtIGhhcyBrZXlzIHRvIHNvbWUgcGlnLWhvdXNlcyBhbmQgd2FudHMgdG8gYnV5IGEgY2VydGFpbiBudW1iZXIgb2YgcGlncy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIGRhdGEgY29uY2VybmluZyBjdXN0b21lcnMgcGxhbm5pbmcgdG8gdmlzaXQgdGhlIGZhcm0gb24gdGhhdCBwYXJ0aWN1bGFyIGRheSBhcmUgYXZhaWxhYmxlIHRvIE1pcmtvIGVhcmx5IGluIHRoZSBtb3JuaW5nIHNvIHRoYXQgaGUgY2FuIG1ha2UgYSBzYWxlcy1wbGFuIGluIG9yZGVyIHRvIG1heGltaXplIHRoZSBudW1iZXIgb2YgcGlncyBzb2xkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nb3JlIHByZWNpc2VseSwgdGhlIHByb2NlZHVyZSBpcyBhcyBmb2xsb3dpbmc6IHRoZSBjdXN0b21lciBhcnJpdmVzLCBvcGVucyBhbGwgcGlnLWhvdXNlcyB0byB3aGljaCBoZSBoYXMgdGhlIGtleSwgTWlya28gc2VsbHMgYSBjZXJ0YWluIG51bWJlciBvZiBwaWdzIGZyb20gYWxsIHRoZSB1bmxvY2tlZCBwaWctaG91c2VzIHRvIGhpbSwgYW5kLCBpZiBNaXJrbyB3YW50cywgaGUgY2FuIHJlZGlzdHJpYnV0ZSB0aGUgcmVtYWluaW5nIHBpZ3MgYWNyb3NzIHRoZSB1bmxvY2tlZCBwaWctaG91c2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbiB1bmxpbWl0ZWQgbnVtYmVyIG9mIHBpZ3MgY2FuIGJlIHBsYWNlZCBpbiBldmVyeSBwaWctaG91c2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGlncyB0aGF0IGhlIGNhbiBzZWxsIG9uIHRoYXQgZGF5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZmlsZSBjb250YWlucyB0d28gaW50ZWdlcnMgTSBhbmQgTiwgMSAmbGU7IE0gJmxlOyAxMDAwLCAxICZsZTsgTiAmbGU7IDEwMCwgbnVtYmVyIG9mIHBpZ2hvdXNlcyBhbmQgbnVtYmVyIG9mIGN1c3RvbWVycy4gUGlnIGhvdXNlcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE0gYW5kIGN1c3RvbWVycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTSBpbnRlZ2VyZXMsIGZvciBlYWNoIHBpZy1ob3VzZSBpbml0aWFsIG51bWJlciBvZiBwaWdzLiBUaGUgbnVtYmVyIG9mIHBpZ3MgaW4gZWFjaCBwaWctaG91c2UgaXMgZ3JlYXRlciBvciBlcXVhbCB0byAwIGFuZCBsZXNzIG9yIGVxdWFsIHRvIDEwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgcmVjb3JkcyBhYm91dCB0aGUgY3VzdG9tZXJzIGluIHRoZSBmb2xsb3dpbmcgZm9ybSAoIHJlY29yZCBhYm91dCB0aGUgaS10aCBjdXN0b21lciBpcyB3cml0dGVuIGluIHRoZSAoaSsyKS10aCBsaW5lKTombmJzcDs8XC9wPlxyXG5cclxuPHA+QSBLPHN1Yj4xPFwvc3ViPiBLPHN1Yj4yPFwvc3ViPiAuLi4gSzxzdWI+QTxcL3N1Yj4gQiZuYnNwOzxcL3A+XHJcblxyXG48cD5JdCBtZWFucyB0aGF0IHRoaXMgY3VzdG9tZXIgaGFzIGtleSB0byB0aGUgcGlnLWhvdXNlcyBtYXJrZWQgd2l0aCB0aGUgbnVtYmVycyBLPHN1Yj4xPFwvc3ViPiwgSzxzdWI+MjxcL3N1Yj4sIC4uLiwgSzxzdWI+QTxcL3N1Yj4gKHNvcnRlZCBub25kZWNyZWFzaW5nbHkgKSBhbmQgdGhhdCBoZSB3YW50cyB0byBidXkgQiBwaWdzLiBOdW1iZXJzIEEgYW5kIEIgY2FuIGJlIGVxdWFsIHRvIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2Ygc29sZCBwaWdzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Final Exam #1 2번