시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 336 136 104 47.706%

문제

종혁이는 자물쇠로 잠긴 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+XHVjNzc0IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNWQwIFx1ZDU1YyBcdWJhODVcdWM1MjkgXHViYzI5XHViYjM4XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI0ZTRcdWM3NDAgXHViYTg3XHViYTg3IFx1YzZiMFx1YjlhYyBcdWM1ZjRcdWMxZTBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzZiMFx1YjlhY1x1YjRlNFx1Yzc0NCBcdWM1ZjAgXHViMmU0XHVjNzRjIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHViOWNjXHVkMDdjXHVjNzU4IFx1YjNmY1x1YzljMFx1Yjk3YyBcdWMwYWNcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YzdhNSBcdWM2YjRcdWM2MDEgXHViYzI5XHVjMmRkXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjMTkwXHViMmQ4XHVjNzc0IFx1YjNjNFx1Y2MyOVx1ZDU3NFx1YzExYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzVmNFx1YzFlMFx1Yjg1YyBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNmIwXHViOWFjXHViNGU0XHVjNzQ0IFx1YzVmMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTkwXHViMmQ4XHVjNWQwXHVhYzhjIFx1YmE4N1x1YmE4NyBcdWIzZmNcdWM5YzBcdWI0ZTRcdWM3NDQgXHVkMzEwXHViMmU0LiAoXHVjMTkwXHViMmQ4XHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2NcdWM3NDQmbmJzcDs8c3Ryb25nPlx1Y2QwOFx1YWNmYzxcL3N0cm9uZz5cdWQ1NThcdWM1ZWMgXHViM2ZjXHVjOWMwXHViOTdjIFx1ZDMxNCBcdWMyMWMgXHVjNWM2XHVjOWMwXHViOWNjIFx1YWRmOCBcdWM3NzRcdWQ1NThcdWI4NWNcdWIyOTQgXHVkMzE0IFx1YzIxOCBcdWM3ODhcdWIyZTQuKTxcL2xpPlxyXG5cdDxsaT5cdWM4ODVcdWQ2MDFcdWM3NzRcdWIyOTQgXHVkMzE0XHVhY2UwIFx1YjBhOFx1Yzc0MCBcdWIzZmNcdWM5YzBcdWI0ZTRcdWM3NDQgXHVkNjA0XHVjN2FjIFx1YzVmNFx1YjgyNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjNmIwXHViOWFjXHViNGU0XHVjNzQ0IFx1YzBjMVx1YjMwMFx1Yjg1YyBcdWM3YWNcdWJkODRcdWJjMzAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1YzZiMFx1YjlhY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzZmNcdWM5YzAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YyBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NzQgXHViYzI5XHViYjM4XHVkNTVjIFx1YjNkOVx1YzU0OCBcdWM4ODVcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwXHViODVjIFx1ZDMxNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2QxZCBcdWIzZmNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNmY1x1YzljMCBcdWM2YjBcdWI5YWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBNKDEmbGU7TSZsZTsxLDAwMClcdWFjZmMgXHVjMTkwXHViMmQ4XHViNGU0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTigxJmxlO04mbGU7MTAwKVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViM2ZjXHVjOWMwXHVjNmIwXHViOWFjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTVx1YmM4OFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YWNlMCBcdWMxOTBcdWIyZDggXHVjNWVkXHVjMmRjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNmY1x1YzljMFx1YzZiMFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZDA4XHVhZTMwIFx1YjNmY1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHViMjk0IDAgXHVjNzc0XHVjMGMxIDEsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc1OCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGkrMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWMxOTBcdWIyZDhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNCBBLCBLMSwgSzIsICZoZWxsaXA7LCBLQSwgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjMTkwXHViMmQ4XHVjNzc0IEsxLCBLMiwgJmhlbGxpcDssIEtBXHViYzg4XHVjOWY4IFx1YzZiMFx1YjlhYyBcdWM1ZjRcdWMxZTBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCBCXHViOWM4XHViOWFjXHVjNzU4IFx1YjNmY1x1YzljMFx1Yjk3YyBcdWMwYWNcdWFlMzggXHVjNmQwXHVkNTVjXHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gQVx1YzY0MCBCXHViMjk0IDAgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWQzMTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzZmNcdWM5YzAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUElHUyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gd29ya3Mgb24gYSBwaWcgZmFybSB0aGF0IGNvbnNpc3RzIG9mIE0gbG9ja2VkIHBpZy1ob3VzZXMgYW5kIE1pcmtvIGNhbiYjMzk7dCB1bmxvY2sgYW55IHBpZ2hvdXNlIGJlY2F1c2UgaGUgZG9lc24mIzM5O3QgaGF2ZSB0aGUga2V5cy4gQ3VzdG9tZXJzIGNvbWUgdG8gdGhlIGZhcm0gb25lIGFmdGVyIGFub3RoZXIuIEVhY2ggb2YgdGhlbSBoYXMga2V5cyB0byBzb21lIHBpZy1ob3VzZXMgYW5kIHdhbnRzIHRvIGJ1eSBhIGNlcnRhaW4gbnVtYmVyIG9mIHBpZ3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsbCBkYXRhIGNvbmNlcm5pbmcgY3VzdG9tZXJzIHBsYW5uaW5nIHRvIHZpc2l0IHRoZSBmYXJtIG9uIHRoYXQgcGFydGljdWxhciBkYXkgYXJlIGF2YWlsYWJsZSB0byBNaXJrbyBlYXJseSBpbiB0aGUgbW9ybmluZyBzbyB0aGF0IGhlIGNhbiBtYWtlIGEgc2FsZXMtcGxhbiBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgbnVtYmVyIG9mIHBpZ3Mgc29sZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9yZSBwcmVjaXNlbHksIHRoZSBwcm9jZWR1cmUgaXMgYXMgZm9sbG93aW5nOiB0aGUgY3VzdG9tZXIgYXJyaXZlcywgb3BlbnMgYWxsIHBpZy1ob3VzZXMgdG8gd2hpY2ggaGUgaGFzIHRoZSBrZXksIE1pcmtvIHNlbGxzIGEgY2VydGFpbiBudW1iZXIgb2YgcGlncyBmcm9tIGFsbCB0aGUgdW5sb2NrZWQgcGlnLWhvdXNlcyB0byBoaW0sIGFuZCwgaWYgTWlya28gd2FudHMsIGhlIGNhbiByZWRpc3RyaWJ1dGUgdGhlIHJlbWFpbmluZyBwaWdzIGFjcm9zcyB0aGUgdW5sb2NrZWQgcGlnLWhvdXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gdW5saW1pdGVkIG51bWJlciBvZiBwaWdzIGNhbiBiZSBwbGFjZWQgaW4gZXZlcnkgcGlnLWhvdXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBpZ3MgdGhhdCBoZSBjYW4gc2VsbCBvbiB0aGF0IGRheS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIGludGVnZXJzIE0gYW5kIE4sIDEgJmxlOyBNICZsZTsgMTAwMCwgMSAmbGU7IE4gJmxlOyAxMDAsIG51bWJlciBvZiBwaWdob3VzZXMgYW5kIG51bWJlciBvZiBjdXN0b21lcnMuIFBpZyBob3VzZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBNIGFuZCBjdXN0b21lcnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIE0gaW50ZWdlcmVzLCBmb3IgZWFjaCBwaWctaG91c2UgaW5pdGlhbCBudW1iZXIgb2YgcGlncy4gVGhlIG51bWJlciBvZiBwaWdzIGluIGVhY2ggcGlnLWhvdXNlIGlzIGdyZWF0ZXIgb3IgZXF1YWwgdG8gMCBhbmQgbGVzcyBvciBlcXVhbCB0byAxMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHJlY29yZHMgYWJvdXQgdGhlIGN1c3RvbWVycyBpbiB0aGUgZm9sbG93aW5nIGZvcm0gKCByZWNvcmQgYWJvdXQgdGhlIGktdGggY3VzdG9tZXIgaXMgd3JpdHRlbiBpbiB0aGUgKGkrMiktdGggbGluZSk6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgSzxzdWI+MTxcL3N1Yj4gSzxzdWI+MjxcL3N1Yj4gLi4uIEs8c3ViPkE8XC9zdWI+IEImbmJzcDs8XC9wPlxyXG5cclxuPHA+SXQgbWVhbnMgdGhhdCB0aGlzIGN1c3RvbWVyIGhhcyBrZXkgdG8gdGhlIHBpZy1ob3VzZXMgbWFya2VkIHdpdGggdGhlIG51bWJlcnMgSzxzdWI+MTxcL3N1Yj4sIEs8c3ViPjI8XC9zdWI+LCAuLi4sIEs8c3ViPkE8XC9zdWI+IChzb3J0ZWQgbm9uZGVjcmVhc2luZ2x5ICkgYW5kIHRoYXQgaGUgd2FudHMgdG8gYnV5IEIgcGlncy4gTnVtYmVycyBBIGFuZCBCIGNhbiBiZSBlcXVhbCB0byAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHNvbGQgcGlncy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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