수업 시간표

프레드 해커의 학교에는 $T \times C$개의 수업이 있으며, 이는 각각 $T$개의 수업으로 이루어진 $C$개의 분류로 나뉩니다. 하루는 1번 분류의 모든 수업이 동시에 진행되는 것으로 시작합니다. 이 수업들이 모두 같은 시각에 끝나면, 그다음에 2번 분류의 모든 수업이 진행되고, 이런 식으로 계속됩니다. 프레드는 각 분류에서 정확히 하나의 수업을 들어야 합니다. 그의 목표는 하루 시간표를 수행하는 데 드는 총 에너지를 최소로 하는 수업 집합을 고르는 것입니다.

시간표의 에너지는, 고른 수업들 자체에 드는 에너지와, 하루 동안 한 수업에서 다음 수업으로 이동하는 데 드는 에너지의 합입니다.

구체적으로, $i$번 분류의 $j$번째 수업을 들으면 $E_{ij}$만큼의 에너지가 듭니다. 강의실들은 하나의 복도를 따라 정수 위치($0$부터 $L$까지)에 있으며, $i$번 분류의 $j$번째 수업은 위치 $P_{ij}$에 있습니다. 프레드는 위치 $0$에서 하루를 시작해, 고른 시간표에 따라 분류 순서대로 수업에서 수업으로 이동하고, 마지막에 위치 $L$에서 나갑니다. 거리 $d$만큼 이동하면 $d$만큼의 에너지가 듭니다.

첫 번째 줄에는 테스트 케이스의 개수 $Z$ ($Z \le 20$)가 주어지고, 그 뒤에 $Z$개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 공백으로 구분된 세 정수 $C$, $T$, $L$로 시작합니다. 이어지는 $C \times T$개의 줄에는 각각 한 수업의 위치와 에너지 소비량이 주어집니다. 처음 $T$개의 줄은 1번 분류의 수업들, 그다음 $T$개의 줄은 2번 분류의 수업들, 이런 식입니다. 같은 분류에 속한 두 수업이 같은 위치에 있는 경우는 없습니다.

• $1 \le C \le 25$
• $1 \le T \le 1000$
• $1 \le L \le 10^6$
• $1 \le E_{ij} \le 10^6$
• $0 \le P_{ij} \le L$

각 테스트 케이스마다, 제약 조건을 만족하는 시간표의 가능한 최소 에너지를 정수 하나로 한 줄에 출력하세요.

이 예시에서 프레드는 하루에 3개의 수업(분류마다 하나)을 들어야 하며, 각 분류에서 2개의 선택지가 있습니다. 복도의 길이는 5입니다.

최소 에너지를 얻는 한 가지 방법:

• 위치 2에 있는 수업으로 갑니다. 지금까지 사용한 총 에너지: 3.
• 다음으로 위치 4에 있는 수업으로 갑니다. 지금까지 사용한 총 에너지: 6.
• 그다음 위치 3에 있는 수업으로 갑니다. 지금까지 사용한 총 에너지: 9.
• 마지막으로 위치 5에서 학교를 나갑니다. 사용한 총 에너지: 11.