먼 은하계에서 프로그래밍 대회가 열린다. 당신의 일은 이 대회 참가자들을 선택하는 것이다.
N 명의 학생들이 참가한다. 그들 각각은 M 개의 다른 카테고리에서 지식들을 가진다. 지식은 실수 값으로 표현할 수 있다. 당신은 많아야 K 명의 학생을 대회에 보낼 수 있다. 그러나 어떤 학생도 한 카테고리 이상에는 참가할 수 없다. 여러명의 학생이 하나의 카테고리에 참가 할 수 있다.
각 학생들에 대해서 각 카테고리별 지식이 주어진다.
각 줄에서 N 쌍 (i,s) 가 주어진다. i 는 학생 번호이고 , s (0 ≤ s ≤ 10) 는 대응되는 카테고리의 지식을 나타내는 양의 실수이다. 쌍은 지식의 내림차순으로 주어진다. 학생들의 번호는 1 에서 N 까지 번호가 부여된다. 각 라인에는 모든 학생은 정확히 한 번 나타난다.
입력 3 2 2 2 3.0 1 0.2 3 0.1 3 1.0 2 0.5 1 0.2 출력 4.0 입력 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 출력 15.0
There are two categories. In the first category, best student is the second one, with knowledge 3.0. He is followed by student numbered 1, with knowledge 0.2, and then number 3, with knowledge 0.1. Best solution is to choose students 2 and 3, in categories 1 and 2, respectively.
출처:coci 2010