체리 피킹

보험은 원래 단순한 발상에서 출발했다. 모두가 공동의 기금에 돈을 내고, 그중 한두 명이 혼자서는 감당할 수 없는 재난을 당했을 때 그 사람을 지원할 만큼의 돈이 모여 있도록 하는 것이다. 가입자가 늘어날수록 관리는 복잡해지고 더 많은 규칙이 필요해졌다. 결국 이런 관리는 이윤을 추구하는 민간 기업이 훨씬 효율적으로 해낼 수 있다는 주장이 나왔다. 하지만 민간 보험사가 이윤을 극대화하려 하는 순간 유인 구조가 달라진다. 보험사는 보험이 가장 절실히 필요한 사람들, 예를 들어 노인이나 기저 질환이 있는 환자를 오히려 가장 꺼리게 된다. 이렇게 가장 수익성 높은 사람만 골라 보험에 넣으려는 행태를 체리 피킹(cherry picking) 이라고 부른다. 이 문제에서는 체리 피킹을 잘 해내는 프로그램을 작성한다.

$n$명의 환자가 주어지며, 각 환자는 $C$개의 범주(예: "남성, 18-30세", "여성, 25-40세" 등) 중 하나에 속한다. 각 환자에 대해, 그 환자가 1년에 낼 수 있는 최대 보험료와 당신이 그 환자에게 1년에 지급해야 할 것으로 예상되는 급여(benefits) 금액을 알고 있다. 각 범주 $c$마다 보험료 $p_c$를 하나씩 정할 수 있다. 범주 $c$에 속한 환자 중 낼 수 있는 최대 금액이 $p_c$ 이상인 환자는 모두 보험에 가입되어 매년 $p_c$를 내고, 그 대가로 당신은 그들의 급여를 지급해야 한다. $p_c$를 감당할 수 없는 환자는 다른 곳으로 떠나 가입되지 않는다.

당신의 이윤은 거둬들인 보험료 총액에서 지급한 급여 총액을 뺀 값이다. 이 이윤이 최대가 되도록 보험료를 정해야 한다. 다만 규제 당국은 전체적으로 최소 $m$명의 환자를 보험에 가입시킬 것을 요구하므로, 보험료 설정은 최소 $m$명이 가입되도록 해야 한다.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 세 정수 $n$, $C$, $m$이 주어진다. $1 \le n \le 1000$은 환자 수, $1 \le C \le 30$은 범주의 수, $0 \le m \le n$은 반드시 가입시켜야 하는 최소 환자 수이다.

이어지는 $n$개의 줄에는 각 환자 $i$를 나타내는 세 정수 $c_i$, $p_i$, $b_i$가 주어진다. $1 \le c_i \le C$는 환자 $i$가 속한 범주, $p_i \ge 0$은 환자 $i$가 낼 수 있는 최대 보험료, $b_i \ge 0$은 그 환자에게 지급해야 하는 급여 금액이다.

각 데이터 집합에 대해 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$는 1부터 시작하는 데이터 집합의 번호이다. 다음 줄에는 각 범주마다 보험료를 하나씩 정하고 최소 $m$명을 가입시켰을 때 얻을 수 있는 최대 이윤을 정수 하나로 출력한다. 연속한 두 데이터 집합 사이에는 빈 줄 하나를 넣어 구분하며, 마지막 데이터 집합 뒤에는 빈 줄을 출력하지 않는다. 최대 이윤은 음수일 수 있다.