시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1076 430 373 42.386%

문제

상근이는 한국 최고의 가수를 뽑는 "나는 위대한 슈퍼스타K"의 감독이다. 상근이는 다음과 같이 참가자를 선발하려고 한다.

"나는 위대한 슈퍼스타K"의 예선에는 N명이 참가했고, 서로 다른 M개 장르에 대한 오디션을 보았다. 심사위원은 모든 참가자의 각 장르에 대한 능력을 점수로 매겼다. 이 점수는 실수로 나타낸다.

본선에는 총 K명이 나갈 수 있다. 각 참가자는 본선에서 단 하나의 장르만 부를 수 있고, 이 장르는 상근이가 정해준다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

모든 참가자의 각 장르에 대한 능력이 주어진다. 이때, 능력의 합이 최대가 되도록 참가자와 장르를 선택하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100)

다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 참가자의 장르에 대한 능력이다. 이 쌍은 능력이 감소하는 순서대로 주어진다. 참가자의 번호는 1부터 N까지 이다.

각 줄에 모든 학생은 한 번씩 등장한다.

출력

첫째 줄에 본선 참가자의 능력의 합을 소수점 첫째자리까지 반올림해 출력한다.

예제 입력 1

4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3

예제 출력 1

15.0
W3sicHJvYmxlbV9pZCI6IjI4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyOTQgXHVjNzA0XHViMzAwXHVkNTVjIFx1YzI4OFx1ZDM3Y1x1YzJhNFx1ZDBjMEsiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NWNcdWFkNmQgXHVjZDVjXHVhY2UwXHVjNzU4IFx1YWMwMFx1YzIxOFx1Yjk3YyBcdWJmNTFcdWIyOTQgJnF1b3Q7XHViMDk4XHViMjk0IFx1YzcwNFx1YjMwMFx1ZDU1YyBcdWMyODhcdWQzN2NcdWMyYTRcdWQwYzBLJnF1b3Q7XHVjNzU4IFx1YWMxMFx1YjNjNVx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjYzM4XHVhYzAwXHVjNzkwXHViOTdjIFx1YzEyMFx1YmMxY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZxdW90O1x1YjA5OFx1YjI5NCBcdWM3MDRcdWIzMDBcdWQ1NWMgXHVjMjg4XHVkMzdjXHVjMmE0XHVkMGMwSyZxdW90O1x1Yzc1OCBcdWM2MDhcdWMxMjBcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc3NCBcdWNjMzhcdWFjMDBcdWQ1ODhcdWFjZTAsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggTVx1YWMxYyBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzYyNFx1YjUxNFx1YzE1OFx1Yzc0NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1YzJlY1x1YzBhY1x1YzcwNFx1YzZkMFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YWMwMSBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJhNVx1YjgyNVx1Yzc0NCBcdWM4MTBcdWMyMThcdWI4NWMgXHViOWU0XHVhY2JjXHViMmU0LiBcdWM3NzQgXHVjODEwXHVjMjE4XHViMjk0IFx1YzJlNFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNmOFx1YzEyMFx1YzVkMFx1YjI5NCBcdWNkMWQgS1x1YmE4NVx1Yzc3NCBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCBcdWJjZjhcdWMxMjBcdWM1ZDBcdWMxMWMgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM3YTVcdWI5NzRcdWI5Y2MgXHViZDgwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWM3YTVcdWI5NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHViOTc0XHViOTdjIFx1YmQ4MFx1Yjk3YyBcdWMyMThcdWIyOTQgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWM1ZWNcdWI3ZWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3YTVcdWI5NzRcdWI5N2MgXHViZDgwXHViOTdjIFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVhYzAxIFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmE1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWIyYTVcdWI4MjVcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNjQwIFx1YzdhNVx1Yjk3NFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVhYzAxIFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCAoaSwgcylcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgaVx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViYzg4XHVkNjM4LCBzXHViMjk0IFx1YWRmOCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjN2E1XHViOTc0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyYTVcdWI4MjVcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWMzMGRcdWM3NDAgXHViMmE1XHViODI1XHVjNzc0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNmOFx1YzEyMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViMmE1XHViODI1XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjY2FiXHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjg2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVLSVBBIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGdhbGF4eSBmYXIsIGZhciBhd2F5LCBhIHByb2dyYW1taW5nIGNvbnRlc3QgaXMgdGFraW5nIHBsYWNlLiBZb3VyIHRhc2sgaXMgdG8gY2hvb3NlIHRoZSBwYXJ0aWNpcGFudHMhJm5ic3A7PFwvcD5cclxuXHJcbjxwPk4gc3R1ZGVudHMgaGF2ZSBhcHBsaWVkLCBhbmQgZWFjaCBvbmUgb2YgdGhlbSBoYXMgc29tZSBrbm93bGVkZ2UgaW4gZWFjaCBvZiBNIGRpZmZlcmVudCBjYXRlZ29yaWVzLiBLbm93bGVkZ2UgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgcmVhbCBudW1iZXIuIFlvdSBjYW4gc2VuZCBhdCBtb3N0IEsgc3R1ZGVudHMgdG8gdGhlIGNvbnRlc3QsIGJ1dCBubyBzdHVkZW50IGNhbiBjb21wZXRlIGluIG1vcmUgdGhhbiBvbmUgY2F0ZWdvcnkuIE11bHRpcGxlIHN0dWRlbnRzIGNhbiBjb21wZXRlIGluIGEgc2luZ2xlIGNhdGVnb3J5LjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBzdHVkZW50LCB0aGVpciBrbm93bGVkZ2Ugb2YgZWFjaCBjYXRlZ29yeSBpcyBnaXZlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q2hvb3NlIHBhcnRpY2lwYW50cyBmb3IgYSBjb250ZXN0IGFuZCBjYXRlZ29yaWVzIHRoZXkgd2lsbCBjb21wZXRlIGluLCBzbyB0aGF0IHRoZSBzdW0gb2Yga25vd2xlZGdlIGlzIG1heGltYWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOLCBNIGFuZCBLICgxICZsZTsgTSAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOICZsZTsgMTAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGRlc2NyaWJlcyBrbm93bGVkZ2UgZm9yIG9uZSBjYXRlZ29yeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBsaW5lLCB0aGVyZSBhcmUgTiBwYWlycyAoaSwgcyksIHdoZXJlIGkgaXMgdGhlIGluZGV4IG9mIHRoZSBzdHVkZW50LCBhbmQgcyBpcyBhIHBvc2l0aXZlIHJlYWwgbnVtYmVyIHJlcHJlc2VudGluZyB0aGVpciBrbm93bGVkZ2Ugb2YgY29ycmVzcG9uZGluZyBjYXRlZ29yeSAoMCAmbGU7IHMgJmxlOyAxMCkuIFBhaXJzIGFyZSBnaXZlbiBpbiBvcmRlciBvZiBkZWNyZWFzaW5nIGtub3dsZWRnZS4gU3R1ZGVudHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIGxpbmUsIGV2ZXJ5IHN0dWRlbnQgd2lsbCBhcGVhciBleGFjdGx5IG9uY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCB0aGUgb25seSBvdXRwdXQgbGluZSBzaG91bGQgY29udGFpbiBtYXhpbXVtIHN1bSBvZiBrbm93bGVkZ2UgY2hvc2VuIHN0dWRlbnRzIGNhbiBoYXZlLCB3aXRoIGV4YWN0bHkgb25lIGRpZ2l0IGluIGRlY2ltYWwgcGFydC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #3 3번