새 장비

시간 제한2초메모리 제한512 MB

요약

작업자를 장비에 배정할 때 작업자 i가 j번 장비에서 a_i·j²+b_i·j+c_i의 비용을 냅니다. 배정 수 k마다 최소 총비용을 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, 수학
정답자: 아직 제출이 없습니다

문제

리틀 Q의 공장에 새 장비 $m$ 대가 들어왔다. 장비에는 $1, 2, \dots, m$ 의 번호가 붙어 있다.

공장에는 작업자 $n$ 명이 있으며 $1, 2, \dots, n$ 의 번호가 붙어 있다. 각 작업자는 장비 한 대에만 배정될 수 있고, 장비 한 대에는 작업자 한 명만 배정될 수 있다. 리틀 Q가 $i$ 번 작업자를 $j$ 번 장비에 배정하면 $a_i \times j^2 + b_i \times j + c_i$ 달러를 지불해야 한다.

모든 $k$ ( $1 \leq k \leq n$ )에 대해, 작업자와 장비의 쌍 $k$ 개를 골라 배정하라. 이때 이 $k$ 명의 작업자가 치르는 총비용이 최소가 되어야 한다.

입력

첫 줄에는 테스트 케이스의 수 $T$ ( $1 \leq T \leq 10$ )가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$ 과 $m$ ( $1 \leq n \leq 50$ , $n \leq m \leq 10^8$ )이 주어진다.

이어지는 $n$ 개의 줄에는 작업자 한 명을 나타내는 정수 $a_i$ , $b_i$ , $c_i$ ( $1 \leq a_i \leq 10$ , $-10^8 \leq b_i \leq 10^8$ , $0 \leq c_i \leq 10^{16}$ , $b_i^2 \leq 4a_ic_i$ )가 주어진다.

출력

각 테스트 케이스마다 정수 $n$ 개를 한 줄에 출력한다. $k$ 번째 정수는 작업자와 장비의 쌍 $k$ 개에 대한 총비용의 최솟값이다.

예제1

예제 1
입력
```
1
3 5
2 3 10
2 -3 10
1 -1 4
```
예상 출력
```
4 15 37
```