시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 486 214 189 47.250%

문제

상근이는 한국 최고의 가수를 뽑는 "나는 위대한 슈퍼스타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
W3sicHJvYmxlbV9pZCI6IjI4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyOTQgXHVjNzA0XHViMzAwXHVkNTVjIFx1YzI4OFx1ZDM3Y1x1YzJhNFx1ZDBjMEsiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NWNcdWFkNmQgXHVjZDVjXHVhY2UwXHVjNzU4IFx1YWMwMFx1YzIxOFx1Yjk3YyBcdWJmNTFcdWIyOTQgJnF1b3Q7XHViMDk4XHViMjk0IFx1YzcwNFx1YjMwMFx1ZDU1YyBcdWMyODhcdWQzN2NcdWMyYTRcdWQwYzBLJnF1b3Q7XHVjNzU4IFx1YWMxMFx1YjNjNVx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjYzM4XHVhYzAwXHVjNzkwXHViOTdjIFx1YzEyMFx1YmMxY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdCZxdW90O1x1YjA5OFx1YjI5NCBcdWM3MDRcdWIzMDBcdWQ1NWMgXHVjMjg4XHVkMzdjXHVjMmE0XHVkMGMwSyZxdW90O1x1Yzc1OCBcdWM2MDhcdWMxMjBcdWM1ZDBcdWIyOTQgTlx1YmE4NVx1Yzc3NCBcdWNjMzhcdWFjMDBcdWQ1ODhcdWFjZTAsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggTVx1YWMxYyBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzYyNFx1YjUxNFx1YzE1OFx1Yzc0NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1YzJlY1x1YzBhY1x1YzcwNFx1YzZkMFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YWMwMSBcdWM3YTVcdWI5NzRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJhNVx1YjgyNVx1Yzc0NCBcdWM4MTBcdWMyMThcdWI4NWMgXHViOWU0XHVhY2JjXHViMmU0LiBcdWM3NzQgXHVjODEwXHVjMjE4XHViMjk0IFx1YzJlNFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmNmOFx1YzEyMFx1YzVkMFx1YjI5NCBcdWNkMWQgS1x1YmE4NVx1Yzc3NCBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCBcdWJjZjhcdWMxMjBcdWM1ZDBcdWMxMWMgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM3YTVcdWI5NzRcdWI5Y2MgXHViZDgwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWM3YTVcdWI5NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHViOTc0XHViOTdjIFx1YmQ4MFx1Yjk3YyBcdWMyMThcdWIyOTQgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWM1ZWNcdWI3ZWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3YTVcdWI5NzRcdWI5N2MgXHViZDgwXHViOTdjIFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVhYzAxIFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmE1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWIyYTVcdWI4MjVcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNjQwIFx1YzdhNVx1Yjk3NFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVhYzAxIFx1YzdhNVx1Yjk3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCAoaSwgcylcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgaVx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViYzg4XHVkNjM4LCBzXHViMjk0IFx1YWRmOCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjN2E1XHViOTc0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyYTVcdWI4MjVcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWMzMGRcdWM3NDAgXHViMmE1XHViODI1XHVjNzc0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNmOFx1YzEyMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHViMmE1XHViODI1XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjY2FiXHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODY1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRUtJUEEiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGEgZ2FsYXh5IGZhciwgZmFyIGF3YXksIGEgcHJvZ3JhbW1pbmcgY29udGVzdCBpcyB0YWtpbmcgcGxhY2UuIFlvdXIgdGFzayBpcyB0byBjaG9vc2UgdGhlIHBhcnRpY2lwYW50cyEmbmJzcDs8XC9wPlxyXG5cclxuPHA+TiBzdHVkZW50cyBoYXZlIGFwcGxpZWQsIGFuZCBlYWNoIG9uZSBvZiB0aGVtIGhhcyBzb21lIGtub3dsZWRnZSBpbiBlYWNoIG9mIE0gZGlmZmVyZW50IGNhdGVnb3JpZXMuIEtub3dsZWRnZSBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSByZWFsIG51bWJlci4gWW91IGNhbiBzZW5kIGF0IG1vc3QgSyBzdHVkZW50cyB0byB0aGUgY29udGVzdCwgYnV0IG5vIHN0dWRlbnQgY2FuIGNvbXBldGUgaW4gbW9yZSB0aGFuIG9uZSBjYXRlZ29yeS4gTXVsdGlwbGUgc3R1ZGVudHMgY2FuIGNvbXBldGUgaW4gYSBzaW5nbGUgY2F0ZWdvcnkuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHN0dWRlbnQsIHRoZWlyIGtub3dsZWRnZSBvZiBlYWNoIGNhdGVnb3J5IGlzIGdpdmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5DaG9vc2UgcGFydGljaXBhbnRzIGZvciBhIGNvbnRlc3QgYW5kIGNhdGVnb3JpZXMgdGhleSB3aWxsIGNvbXBldGUgaW4sIHNvIHRoYXQgdGhlIHN1bSBvZiBrbm93bGVkZ2UgaXMgbWF4aW1hbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4sIE0gYW5kIEsgKDEgJmxlOyBNICZsZTsgMTAwLCAxICZsZTsgSyAmbGU7IE4gJmxlOyAxMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE0gbGluZXMgZGVzY3JpYmVzIGtub3dsZWRnZSBmb3Igb25lIGNhdGVnb3J5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIGxpbmUsIHRoZXJlIGFyZSBOIHBhaXJzIChpLCBzKSwgd2hlcmUgaSBpcyB0aGUgaW5kZXggb2YgdGhlIHN0dWRlbnQsIGFuZCBzIGlzIGEgcG9zaXRpdmUgcmVhbCBudW1iZXIgcmVwcmVzZW50aW5nIHRoZWlyIGtub3dsZWRnZSBvZiBjb3JyZXNwb25kaW5nIGNhdGVnb3J5ICgwICZsZTsgcyAmbGU7IDEwKS4gUGFpcnMgYXJlIGdpdmVuIGluIG9yZGVyIG9mIGRlY3JlYXNpbmcga25vd2xlZGdlLiBTdHVkZW50cyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGVhY2ggbGluZSwgZXZlcnkgc3R1ZGVudCB3aWxsIGFwZWFyIGV4YWN0bHkgb25jZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIHRoZSBvbmx5IG91dHB1dCBsaW5lIHNob3VsZCBjb250YWluIG1heGltdW0gc3VtIG9mIGtub3dsZWRnZSBjaG9zZW4gc3R1ZGVudHMgY2FuIGhhdmUsIHdpdGggZXhhY3RseSBvbmUgZGlnaXQgaW4gZGVjaW1hbCBwYXJ0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==