행글라이딩

2020 행글라이딩 세계선수권대회가 다음 봄 플로리다에서 열린다! (산이 있어야 하는 스포츠를 플로리다에서 연다니 이상하게 보일 수 있지만, 행글라이더는 다른 항공기에 끌려 고도까지 올라갈 수 있다.) 대회는 여러 과제로 나뉘며, 과제를 성공하면 조종사는 그 과제의 점수를 얻는다. 과제마다 점수는 전부 주어지거나 전혀 주어지지 않는다. 모든 조종사는 과제마다 성공 확률을 가진다. 조종사의 점수는 대회가 끝났을 때 성공한 과제 점수의 합이다.

올해 조직위원회는 적당한 과제 수를 정하지 못해서, 과제들의 시간대가 서로 겹친다. 어느 시점에든 여러 과제가 동시에 진행될 수 있지만, 조종사는 그 시점에 한 과제만 고를 수 있다. 조종사는 이 제약 안에서 원하는 만큼 과제에 참가할 수 있다. 조종사는 자신의 강점과 약점을 알고 있으며, 기대 점수가 최대가 되도록 과제를 고른다.

대회 채점 소프트웨어를 도우면 무료 행글라이딩 강습을 받을 수 있다. 조직위원회는 무엇보다도 우승자를 미리 예측할 수 있는 소프트웨어를 원한다.

각 과제에는 시간대와 성공 시 받는 점수가 있고, 각 조종사에게는 과제별 성공 확률이 있다. 과제 집합과 조종사 목록이 주어졌을 때, 조종사마다 기대 점수를 계산하고 상위 3개의 기대 점수를 보고하라.

첫 줄에는 정수 $t$ ($1 \le t \le 10000$)와 $p$ ($3 \le p \le 100$)가 공백으로 구분되어 주어진다. $t$는 과제 수, $p$는 조종사 수이다.

다음 $t$개 줄에 과제 정보가 주어진다. 각 줄에는 정수 $s$, $e$, $a$가 공백으로 구분되어 있으며, $0 \le s < e \le 10000$이다. $s$는 과제 시작 시각, $e$는 과제 종료 시각이고, 둘 다 대회 시작 후 경과한 분 단위이다. $a$ ($1 \le a \le 100$)는 과제를 성공했을 때 받는 점수이다. 과제의 시작과 종료 시각은 양 끝을 포함하지 않는다. 한 과제가 시각 $T$에 끝나고 다른 과제가 시각 $T$에 시작하면, 조종사는 두 과제에 모두 참가할 수 있다.

과제 정보 뒤에는 조종사마다 $t$개 줄씩 이어진다. 처음 $t$개 줄은 1번 조종사의 과제별 성공 확률이고, 다음 $t$개 줄은 2번 조종사의 값이며, 이런 식으로 이어진다. 확률은 0 이상 1 이하의 실수이다.

상위 3명의 조종사를 출력한다. 기대 점수가 높은 순서대로 한 줄에 조종사 번호, 공백, 기대 점수를 출력한다. 기대 점수는 소수점 아래 둘째 자리에서 반올림한다(예: 42.494는 42.49, 42.495는 42.50으로 출력). 조종사 번호는 0이 아니라 1부터 시작한다.