시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB166491366753.403%

문제

N(3 ≤ N ≤ 200)명의 사람이 파티를 하려고 한다. 각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각각의 음식의 종류는 1부터 D(5 ≤ D ≤ 100)까지의 정수로 표현된다 하자. 파티를 위해서 각각의 사람이 요리를 해서 가져오기로 했는데, 가급적이면 많은 양(접시의 수로 계산)의 음식을 파티에 준비하려 한다.

그렇다면 각각의 음식을 최대한 많이 준비해 오면 되겠지만, 우선 각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다. 각각의 사람은 최대 K(1 ≤ K ≤ 5)개의 접시밖에 가져올 수 없다고 하자. 이때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자. 즉, 한 사람이 세 접시의 스테이크를 가져올 수 없지만, 한 접시의 스테이크, 한 접시의 샐러드, 한 접시의 파스타를 가져올 수 있다.

또한 각 음식의 종류마다도 가져올 수 있는 양에 제한이 있다. 사전에 파티 참석자들에게 음식 선호도 조사를 하여 낭비되는 음식이 없도록 양을 정했다.

이와 같은 제한들이 주어졌을 때, 파티에 준비될 수 있는 접시(물론 음식이 담겨있는)의 개수의 최댓값을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개의 줄에는 각 사람이 요리할 줄 아는 음식의 종류 개수 Z(1 ≤ Z ≤ D)와, Z개의 정수로 요리할 줄 아는 음식의 번호가 주어진다.

출력

첫째 줄에 파티에 준비될 수 있는 접시 개수의 최댓값을 출력한다.

예제 입력 1

4 3 5
2 2 2 2 3
4 1 2 3 4
4 2 3 4 5
3 1 2 4
3 1 2 3

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjIzNjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWQyZjAiLCJkZXNjcmlwdGlvbiI6IjxwPk4oMyAmbGU7IE4gJmxlOyAyMDApXHViYTg1XHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWQzMGNcdWQyZjBcdWI5N2MgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWJhODcgXHVjODg1XHViOTU4XHVjNzU4IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM2OTRcdWI5YWNcdWQ1NjAgXHVjOTA0IFx1YzU0OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzc0Y1x1YzJkZFx1Yzc1OCBcdWM4ODVcdWI5NThcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBEKDUgJmxlOyBEICZsZTsgMTAwKVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0IFx1ZDU1OFx1Yzc5MC4gXHVkMzBjXHVkMmYwXHViOTdjIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzY5NFx1YjlhY1x1Yjk3YyBcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjODM4XHVjNjI0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHVhYzAwXHVhZTA5XHVjODAxXHVjNzc0XHViYTc0IFx1YjljZVx1Yzc0MCBcdWM1OTEoXHVjODExXHVjMmRjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWFjYzRcdWMwYjApXHVjNzU4IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjOTAwXHViZTQ0XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViODA3XHViMmU0XHViYTc0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc3NCBcdWM5MDBcdWJlNDRcdWQ1NzQgXHVjNjI0XHViYTc0IFx1YjQxOFx1YWNhMFx1YzljMFx1YjljYywgXHVjNmIwXHVjMTIwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzU4IFx1YzU5MVx1YzVkMCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBLKDEgJmxlOyBLICZsZTsgNSlcdWFjMWNcdWM3NTggXHVjODExXHVjMmRjXHViYzE2XHVjNWQwIFx1YWMwMFx1YzgzOFx1YzYyYyBcdWMyMTggXHVjNWM2XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjIFx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjNzRjXHVjMmRkXHVjNzQwIFx1ZDU1YyBcdWM4MTFcdWMyZGNcdWJjMTZcdWM1ZDAgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM5ODksIFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTM4IFx1YzgxMVx1YzJkY1x1Yzc1OCBcdWMyYTRcdWQxNGNcdWM3NzRcdWQwNmNcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM1YzZcdWM5YzBcdWI5Y2MsIFx1ZDU1YyBcdWM4MTFcdWMyZGNcdWM3NTggXHVjMmE0XHVkMTRjXHVjNzc0XHVkMDZjLCBcdWQ1NWMgXHVjODExXHVjMmRjXHVjNzU4IFx1YzBkMFx1YjdlY1x1YjRkYywgXHVkNTVjIFx1YzgxMVx1YzJkY1x1Yzc1OCBcdWQzMGNcdWMyYTRcdWQwYzBcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1YjljOFx1YjJlNFx1YjNjNCBcdWFjMDBcdWM4MzhcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1OTFcdWM1ZDAgXHVjODFjXHVkNTVjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjMGFjXHVjODA0XHVjNWQwIFx1ZDMwY1x1ZDJmMCBcdWNjMzhcdWMxMWRcdWM3OTBcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNzRjXHVjMmRkIFx1YzEyMFx1ZDYzOFx1YjNjNCBcdWM4NzBcdWMwYWNcdWI5N2MgXHVkNTU4XHVjNWVjIFx1YjBhZFx1YmU0NFx1YjQxOFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM3NzQgXHVjNWM2XHViM2M0XHViODVkIFx1YzU5MVx1Yzc0NCBcdWM4MTVcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODFjXHVkNTVjXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDMwY1x1ZDJmMFx1YzVkMCBcdWM5MDBcdWJlNDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTFcdWMyZGMoXHViYjNjXHViODYwIFx1Yzc0Y1x1YzJkZFx1Yzc3NCBcdWIyZjRcdWFjYThcdWM3ODhcdWIyOTQpXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE4sIEssIERcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IERcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IFx1YWMwMSBcdWM3NGNcdWMyZGRcdWM3NTggXHVjODg1XHViOTU4XHViOWM4XHViMmU0IFx1YWMwMFx1YzgzOFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MWNcdWQ1NWNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNjk0XHViOWFjXHVkNTYwIFx1YzkwNCBcdWM1NDRcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzU4IFx1Yzg4NVx1Yjk1OCBcdWFjMWNcdWMyMTggWigxICZsZTsgWiAmbGU7IEQpXHVjNjQwLCBaXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM2OTRcdWI5YWNcdWQ1NjAgXHVjOTA0IFx1YzU0NFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDMwY1x1ZDJmMFx1YzVkMCBcdWM5MDBcdWJlNDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTFcdWMyZGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjM2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5ldyBZZWFycyBQYXJ0eSIsImRlc2NyaXB0aW9uIjoiPHA+QSBncm91cCBvZiAmbmJzcDtOICgzICZsdDs9IE4gJmx0Oz0gMjAwKSBjb3dzIGlzIGhhdmluZyBhIE5ldyBZZWFyJiMzOTtzIHBhcnR5LiAmbmJzcDtFYWNoIGNvdyBpcyBhYmxlJm5ic3A7dG8gY29vayBzZXZlcmFsIGRpZmZlcmVudCBraW5kcyBvZiBmb29kIChpbiB1bml0cyBjYWxsZWQgYSAmcXVvdDtkaXNoJnF1b3Q7KS4gVGhlcmUgYXJlIGEmbmJzcDt0b3RhbCBvZiBEICg1ICZsdDs9IEQgJmx0Oz0gMTAwKSBkaWZmZXJlbnQga2luZHMgb2YgZm9vZC4gJm5ic3A7RWFjaCBraW5kIG9mIGZvb2QgaXMgZGVub3RlZCZuYnNwO2J5IGFuIGludGVnZXIgaW4gdGhlIHJhbmdlIDEuLkQuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dyZGluYXRvciB3YW50cyB0byBtYXhpbWl6ZSB0aGUgdG90YWwgbnVtYmVyIG9mIGRpc2hlcyBicm91Z2h0IHRvIHRoZSBwYXJ0eSwmbmJzcDtidXQgaGFzIHNwZWNpZmllZCBhIGxpbWl0IGZvciB0aGUgbnVtYmVyIG9mIGRpc2hlcyBvZiBlYWNoIHR5cGUuIEVhY2ggY293IGNhbiBicmluZyBLICgxICZsdDs9IEsgJmx0Oz0gNSkgZGlzaGVzLCBidXQgdGhleSBtdXN0IGJlIGRpZmZlcmVudCBmcm9tIGVhY2ggb3RoZXIgKHNoZSBjYW4mIzM5O3QgYnJpbmcgMyBib3ZpbmUgcGllcywgZm9yIGV4YW1wbGUsIGJ1dCBzaGUgY291bGQgYnJpbmcgYSBwaWUsIHNvbWUgYnJlYWQsIGFuZCBzb21lIG5pY2UmbmJzcDthbGZhbGZhIGluIG9yYW5nZSBzYXVjZSkuICZuYnNwO1doYXQgaXMgdGhlIG1heGltdW0gYW1vdW50IG9mIGZvb2QgdGhhdCBjYW4gYmUgYnJvdWdodD88XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBpbnRlZ2VyczogTiwgSywgYW5kIEQ8XC9saT5cclxuXHQ8bGk+TGluZSAyOiBEIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyczogdGhlIGxpbWl0IG9uIHRvdGFsIG51bWJlciBvZiBlYWNoIG9mIHRoZSB2YXJpb3VzIGRpc2hlcyB0aGF0IGNhbiBiZSBicm91Z2h0IHRvIHRoZSBwYXJ0eTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAzLi5OKzI6IEVhY2ggbGluZSBjb250YWlucyBhbiBpbml0aWFsIGludGVnZXIgWiAoMSAmbHQ7PSBaICZsdDs9IEQpIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGRpc2hlcyBhIGNvdyBjYW4gcHJlcGFyZTsgdGhlIHJlc3Qgb2YgdGhlIGxpbmUgY29udGFpbnMgWiBpbnRlZ2VycyB0aGF0IGFyZSB0aGUgZm9vZCBpZGVudGlmaWVycywgZm9vZCB0eXBlIDEgZmlyc3QsIGZvb2QgdHlwZSAyIHNlY29uZCwgZXRjLi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGRpc2hlcyB0aGF0IGNhbiZuYnNwO2JlIGJyb3VnaHQgdG8gdGhlIHBhcnR5LjxcL3A+XHJcbiIsImhpbnQiOiI8cHJlPlxyXG5kYXRhLi4uLi4uICAgICBleHBsYW5hdGlvbi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLlxyXG40IDMgNSAgICAgICAgICA0IGNvd3MsIGVhY2ggY293IGJyaW5ncyB1cCB0byAzIGRpc2hlcywgNSBkaWZmZXJlbnQgZm9vZCB0eXBlc1xyXG4yIDIgMiAyIDMgICAgICBtYXggZm9yIHBhcnR5IG9mIDIgZGlzaGVzIGZvb2QgdHlwZXMgMS4uNDsgMyBkaXNoZXMgb2YgZm9vZCA1XHJcbjQgMSAyIDMgNCAgICAgIFRoaXMgY293IGNhbiBjb29rIDQgZGlmZmVyZW50IGZvb2RzICgxLCAyLCAzLCA0KVxyXG40IDIgMyA0IDUgICAgICBUaGlzIGNvdyBjYW4gY29vayA0IGRpZmZlcmVudCBmb29kcyAoMiwgMywgNCwgNSlcclxuMyAxIDIgNCAgICAgICAgVGhpcyBjb3cgY2FuIGNvb2sgMyBkaWZmZXJlbnQgZm9vZHMgKDEsIDIsIDQpXHJcbjMgMSAyIDMgICAgICAgIFRoaXMgY293IGNhbiBjb29rIDMgZGlmZmVyZW50IGZvb2RzICgxLCAyLCAzKVxyXG48XC9wcmU+XHJcblxyXG48cD5Db3cgMSBicmluZ3MgZm9vZHMgMyBhbmQgNDsgY293IDIgYnJpbmdzIGZvb2RzIDMsIDQgYW5kIDU7IGNvdyAzIGJyaW5ncyBmb29kcyAxIGFuZCAyOyBhbmQgY293IDQgYnJpbmdzIGZvb2RzIDEgYW5kIDIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO Winter 2002 Contest > Green 2번

  • 문제의 오타를 찾은 사람: jwvg0425
  • 어색한 표현을 찾은 사람: upple1