골프장

뉴 라이트(New Light) 아파트 단지 근처에 골프장을 지으려고 합니다. 여러 후보 부지를 조사했으며, 각 후보에 대해 수용 인원(그 골프장이 받을 수 있는 고객 수)과 건설 비용을 알고 있습니다.

뉴 라이트에는 골프를 치고 싶어 하는 주민이 여러 명 있습니다. 후보 부지 중 일부를 골라 골프장을 짓고, 모든 고객을 지어진 골프장 중 하나에 배정하여 전체 고객을 만족시키되, 총비용을 최대한 작게 만들어야 합니다.

총비용은 두 부분으로 이루어집니다.

• 고객들이 이용하는 골프장까지의 연결 비용 합계
• 지어진 골프장들의 건설 비용 합계

아래 예시를 살펴봅시다.

후보 부지와 뉴 라이트의 연결은 별 모양(star) 그래프를 이룹니다. 뉴 라이트가 가운데 정점이고, 나머지 정점은 모두 후보 부지입니다. 뉴 라이트 옆의 숫자는 골프를 치려는 고객 수입니다. 후보 부지 옆의 두 숫자는 그 부지의 건설 비용과 수용 인원입니다. 간선 위의 숫자는 뉴 라이트와 그 후보 부지 사이의 거리이며, 그 골프장을 이용하는 고객은 이 거리를 연결 비용으로 냅니다.

이 예시에서 최적해는 아래 그림과 같습니다. 골프장 두 개를 짓고, 건설 비용은 각각 $6$과 $2$입니다. 두 명의 고객은 연결 비용(거리)이 $1$인 골프장을, 나머지 세 명은 연결 비용이 $2$인 골프장을 이용합니다. 건설 비용 합계는 $6 + 2 = 8$이고, 연결 비용 합계는 $1 + 1 + 2 + 2 + 2 = 8$이므로, 총비용은 $8 + 8 = 16$입니다.

예제에서 첫 번째 테스트 케이스가 위 그림에 해당합니다.

입력은 표준 입력으로 주어지며 $T$개의 테스트 케이스로 이루어집니다. 첫 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어집니다.

각 테스트 케이스의 형식은 다음과 같습니다. 첫 줄에는 후보 부지의 수를 나타내는 양의 정수 $N$ ($1 \le N \le 500$)이 주어집니다. 둘째 줄에는 고객 수를 나타내는 양의 정수 $P$ ($1 \le P \le 10000$)가 주어집니다. 이어지는 $N$개의 줄에는 각 후보 부지에 대한 세 개의 양의 정수가 한 칸의 공백으로 구분되어 주어지며, 순서대로 뉴 라이트에서 그 부지까지의 거리, 골프장의 건설 비용, 골프장의 수용 인원입니다. 모든 정수는 $1$ 이상 $10000$ 이하입니다.

후보 부지들의 수용 인원 합계는 항상 $P$ 이상이므로 모든 고객을 배정할 수 있습니다.

표준 출력으로 출력합니다. 각 테스트 케이스마다, 연결 비용 합계와 건설 비용 합계를 더한 값의 최솟값을 한 줄에 하나씩 출력합니다.