프로젝트 인력 배치

어떤 회사가 이번 주 안에 프로젝트 $m$개를 끝내려고 한다. 회사는 직업소개소에서 일주일 계약으로 외부 인력을 최대 $n$명까지 고용할 수 있다.

외부 인력 한 명의 급여는 salary 유로다. 다만 그 사람이 투입된 프로젝트가 기한 안에 끝나지 않으면 회사는 그 사람에게 급여를 지급하지 않는다.

회사는 경험으로 각 프로젝트가 일주일 안에 끝날 확률을 투입 인원 수의 함수로 알고 있다. 확률은 백분율 $p_{ij}$로 주어진다. $i$($1 \le i \le m$)는 프로젝트 번호, $j$는 그 프로젝트에 투입한 인원 수다. 프로젝트 $i$에 아무도 투입하지 않으면 확률 $p_{i0}$은 0퍼센트다.

프로젝트 $i$가 일주일 안에 끝나면 회사는 reward($i$) 유로를 번다. 기한을 넘기면 punishment($i$) 유로를 벌금으로 낸다.

어떤 일이 기한 안에 끝날 확률을 $p$($0 < p < 1$), 그때의 이익을 $E_1$, 끝내지 못했을 때의 (음수인) 이익을 $E_2$라고 하자. 그러면 그 일의 기대 이익은 $p \times E_1 + (1 - p) \times E_2$다.

회사는 주말 시점의 총 기대 이익이 최대가 되도록 외부 인력을 몇 명 고용해서 프로젝트에 어떻게 나눌지 정한다. 최적 인원 수는 최대 기대 이익을 얻는 데 필요한 총 인원 수다. 이 인원 수를 구하여라. 쓸 수 있는 인력은 최대 $n$명이고, 고용된 사람은 정확히 한 프로젝트만 맡는다. 따라서 총 인원 수는 각 프로젝트에 배정한 인원의 합이다.

첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 프로젝트의 개수 $m$이 주어진다. ($1 \le m \le 100$)
• 둘째 줄에 고용할 수 있는 최대 인원 $n$이 주어진다. ($0 \le n \le 100$)
• 셋째 줄에 인력 한 명의 급여 salary가 유로 단위로 주어진다. salary는 0 이상 1000 이하의 정수다.
• 다음 $m$개 줄에는 프로젝트 정보가 한 줄씩 주어진다. $i$번째 줄에는 정수 $n$개 $p_{i1}, p_{i2}, \dots, p_{in}$이 오고, 이어서 프로젝트 $i$의 reward와 punishment가 온다. 확률은 모두 0 이상 100 이하의 백분율이고, reward와 punishment는 0 이상 100000 이하의 유로 금액이다. 한 줄 안의 값은 모두 공백 하나로 구분된다.

각 테스트 케이스마다 두 줄을 출력한다.

• 첫 줄에는 최대 기대 이익을 유로센트 단위로 출력한다. 확률이 정수 백분율이고 금액이 정수 유로이므로 이 값은 항상 유로센트 단위의 정수다.
• 둘째 줄에는 그 최대 기대 이익을 얻으려면 고용해야 하는 외부 인력의 총 인원 수를 출력한다. 서로 다른 총 인원 수로 같은 최대 기대 이익에 도달하면 그 인원 수를 모두 오름차순으로 공백 하나씩 두고 출력한다.