시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 456 198 175 46.543%

문제

상근이는 한국 최고의 가수를 뽑는 "나는 위대한 슈퍼스타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
W3sicHJvYmxlbV9pZCI6IjI4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyOTQgXHVjNzA0XHViMzAwXHVkNTVjIFx1YzI4OFx1ZDM3Y1x1YzJhNFx1ZDBjMEsiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NWNcdWFkNmQgXHVjZDVjXHVhY2UwXHVjNzU4IFx1YWMwMFx1YzIxOFx1Yjk3YyBcdWJmNTFcdWIyOTQgJnF1b3Q7XHViMDk4XHViMjk0IFx1YzcwNFx1YjMwMFx1ZDU1YyBcdWMyODhcdWQzN2NcdWMyYTRcdWQwYzBLJnF1b3Q7XHVjNzU4IFx1YWMxMFx1YjNjNVx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjYzM4XHVhYzAwXHVjNzkwXHViOTdjIFx1YzEyMFx1YmMxY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdCZxdW90O1x1YjA5OFx1YjI5NCBcdWM3MDRcdWIzMDBcdWQ1NWMgXHVjMjg4XHVkMzdjXHVjMmE0XHVkMGMwSyZxdW90O1x1Yzc1OCBcdWM2MDhcdWMxMjBcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc3NCBcdWNjMzhcdWFjMDBcdWQ1ODhcdWFjZTAsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggTVx1YWMxYyBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzYyNFx1YjUxNFx1YzE1OFx1Yzc0NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1YzJlY1x1YzBhY1x1YzcwNFx1YzZkMFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YWMwMSBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJhNVx1YjgyNVx1Yzc0NCBcdWM4MTBcdWMyMThcdWI4NWMgXHViOWU0XHVhY2JjXHViMmU0LiBcdWM3NzQgXHVjODEwXHVjMjE4XHViMjk0IFx1YzJlNFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmNmOFx1YzEyMFx1YzVkMFx1YjI5NCBcdWNkMWQgS1x1YmE4NVx1Yzc3NCBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCBcdWJjZjhcdWMxMjBcdWM1ZDBcdWMxMWMgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM3YTVcdWI5NzRcdWI5Y2MgXHViZDgwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWM3YTVcdWI5NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHViOTc0XHViOTdjIFx1YmQ4MFx1Yjk3YyBcdWMyMThcdWIyOTQgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWM1ZWNcdWI3ZWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3YTVcdWI5NzRcdWI5N2MgXHViZDgwXHViOTdjIFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVhYzAxIFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmE1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViMmE1XHViODI1XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YzY0MCBcdWM3YTVcdWI5NzRcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0gJmxlOyAxMDAsIDEgJmxlOyBLICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1YWMwMSBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1Yzc1OCBcdWIyYTVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggKGksIHMpXHVjMzBkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIGlcdWIyOTQgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YmM4OFx1ZDYzOCwgc1x1YjI5NCBcdWFkZjggXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmE1XHViODI1XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjMzBkXHVjNzQwIFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWFjMTBcdWMxOGNcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjhcdWMxMjAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YjJhNVx1YjgyNVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2NhYlx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVLSVBBIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGdhbGF4eSBmYXIsIGZhciBhd2F5LCBhIHByb2dyYW1taW5nIGNvbnRlc3QgaXMgdGFraW5nIHBsYWNlLiBZb3VyIHRhc2sgaXMgdG8gY2hvb3NlIHRoZSBwYXJ0aWNpcGFudHMhJm5ic3A7PFwvcD5cclxuXHJcbjxwPk4gc3R1ZGVudHMgaGF2ZSBhcHBsaWVkLCBhbmQgZWFjaCBvbmUgb2YgdGhlbSBoYXMgc29tZSBrbm93bGVkZ2UgaW4gZWFjaCBvZiBNIGRpZmZlcmVudCBjYXRlZ29yaWVzLiBLbm93bGVkZ2UgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgcmVhbCBudW1iZXIuIFlvdSBjYW4gc2VuZCBhdCBtb3N0IEsgc3R1ZGVudHMgdG8gdGhlIGNvbnRlc3QsIGJ1dCBubyBzdHVkZW50IGNhbiBjb21wZXRlIGluIG1vcmUgdGhhbiBvbmUgY2F0ZWdvcnkuIE11bHRpcGxlIHN0dWRlbnRzIGNhbiBjb21wZXRlIGluIGEgc2luZ2xlIGNhdGVnb3J5LjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBzdHVkZW50LCB0aGVpciBrbm93bGVkZ2Ugb2YgZWFjaCBjYXRlZ29yeSBpcyBnaXZlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q2hvb3NlIHBhcnRpY2lwYW50cyBmb3IgYSBjb250ZXN0IGFuZCBjYXRlZ29yaWVzIHRoZXkgd2lsbCBjb21wZXRlIGluLCBzbyB0aGF0IHRoZSBzdW0gb2Yga25vd2xlZGdlIGlzIG1heGltYWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOLCBNIGFuZCBLICgxICZsZTsgTSAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOICZsZTsgMTAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGRlc2NyaWJlcyBrbm93bGVkZ2UgZm9yIG9uZSBjYXRlZ29yeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBsaW5lLCB0aGVyZSBhcmUgTiBwYWlycyAoaSwgcyksIHdoZXJlIGkgaXMgdGhlIGluZGV4IG9mIHRoZSBzdHVkZW50LCBhbmQgcyBpcyBhIHBvc2l0aXZlIHJlYWwgbnVtYmVyIHJlcHJlc2VudGluZyB0aGVpciBrbm93bGVkZ2Ugb2YgY29ycmVzcG9uZGluZyBjYXRlZ29yeSAoMCAmbGU7IHMgJmxlOyAxMCkuIFBhaXJzIGFyZSBnaXZlbiBpbiBvcmRlciBvZiBkZWNyZWFzaW5nIGtub3dsZWRnZS4gU3R1ZGVudHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIGxpbmUsIGV2ZXJ5IHN0dWRlbnQgd2lsbCBhcGVhciBleGFjdGx5IG9uY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCB0aGUgb25seSBvdXRwdXQgbGluZSBzaG91bGQgY29udGFpbiBtYXhpbXVtIHN1bSBvZiBrbm93bGVkZ2UgY2hvc2VuIHN0dWRlbnRzIGNhbiBoYXZlLCB3aXRoIGV4YWN0bHkgb25lIGRpZ2l0IGluIGRlY2ltYWwgcGFydC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=