잔해 정리

큰 허리케인이 지나간 뒤 도로를 정리하는 데는 보통 몇 달, 길게는 몇 년이 걸린다. 진흙과 잔해가 많이 쌓이고, 오염물질(이전 문제 참조)이 있으면 작업이 더 어려워진다. 이 문제에서는 도로를 따라 놓인 잔해를 치우는 작업팀의 계획을 세운다.

정리 작업에서는 불도저로 잔해를 몇 개의 큰 더미로 모은 뒤, 트럭으로 더미를 하나씩 실어 나른다. 트럭이 더미 하나를 가져가는 데는 실은 양과 관계없이 T의 시간이 든다. 운전자는 더미마다 서류 작업을 많이 해야 하고, 현장까지 운전하거나 싣는 시간은 그에 비해 무시할 만하다.

더미는 불도저로 잔해를 옮겨 만든다. 각 위치에 처음 놓인 잔해의 양이 주어지며, 어디로 옮길지는 직접 정한다. 잔해를 전혀 옮기지 않아도 된다. 다만 그러면 처음의 각 더미를 따로 가져가야 하며, 이것이 최적이 아닐 수 있다. 잔해 u를 거리 d만큼 옮기는 데 불도저는 $u \times d$의 시간이 걸린다. 각 위치의 잔해 양이 주어졌을 때, 불도저로 더미를 만들고 트럭으로 가져가는 데 드는 총 시간의 최솟값을 구한다. 트럭은 불도저 작업이 모두 끝난 뒤에야 출발한다.

첫 줄에 데이터 세트의 수 $1 \le K \le 100$이 주어진다. 이어서 K개의 데이터 세트가 주어진다.

각 데이터 세트의 첫 줄에는 정수 n과 T가 주어진다. $1 \le n \le 200$은 원래 잔해 지점의 개수이고, $0 \le T \le 1000000$은 트럭이 한 번 운행하는 데 걸리는 시간이다.

다음 줄에는 정수 2n개 $\ell_i$, $d_i$가 주어진다. $0 \le \ell_i \le 1000000$은 도로를 따라 i번째 잔해 수거 지점의 위치이고, $1 \le d_i \le 1000000$은 그 지점에 있는 잔해의 양이다. 쌍은 $\ell_i$가 엄격하게 증가하는 순서로 정렬되어 있다.

각 데이터 세트마다 Data Set x:라는 줄을 출력한다. x는 데이터 세트의 번호이다. 다음 줄에는 정리에 걸리는 최소 총 시간(불도저 시간과 트럭 시간의 합)을 출력한다. 각 데이터 세트의 출력 뒤에는 빈 줄을 하나 출력한다.