Cleanup

It often takes months or even years to clean up after a major hurricane. Mud and debris pile up, and contaminants (see the previous problem) can make the work harder. This problem asks you to plan how a cleanup crew clears debris along one road.

Cleanup uses a bulldozer to push debris into a few large piles, and then trucks load the piles. Each pile a truck picks up takes a fixed time T, no matter how much debris it holds. The driver must complete a lot of paperwork for each pile, while driving there and loading take negligible time.

The piles are formed by bulldozing debris. You are given how much debris starts at each location, and you decide where to move it. You may move nothing at all, but then each original pile must be picked up separately, which may not be optimal. Moving u units of debris a distance d with the bulldozer takes $u \times d$ time. Given the debris at each location, compute the minimum total time to form the piles with the bulldozer and then pick them up with trucks. The trucks start only after the bulldozer has finished.

The first line contains the number of data sets $1 \le K \le 100$. Then K data sets follow.

The first line of each data set contains two integers n and T, where $1 \le n \le 200$ is the number of original debris locations and $0 \le T \le 1000000$ is the time for one truck trip.

The next line contains 2n integers $\ell_i$ and $d_i$. Here $0 \le \ell_i \le 1000000$ is the location along the road of the i-th debris collection point, and $1 \le d_i \le 1000000$ is the amount of debris there. The pairs are sorted by strictly increasing $\ell_i$.

For each data set, print a line Data Set x: where x is the data set number. On the next line, print the minimum total time for the cleanup (bulldozer time plus truck time). Print a blank line after each data set.