Formula Race

In a popular motorsport, a race car must complete exactly $N$ full laps of the track. Every lap burns a fixed amount of fuel, so we measure fuel by the number of laps it still allows. Having $i$ units of fuel in the tank means the car can drive $i$ more laps without refueling, and each completed lap lowers the fuel by $1$. The tank can hold at most $N$ units.

After finishing a lap, the car may (but need not) enter the pit lane for $P$ seconds. During a pit stop the crew may perform any of the following:

• Add fuel to the tank (never above $N$)
• Change the type of tire the car runs on

The team has two types of tires. A lap's duration depends on:

• The amount of fuel currently in the tank
• The type of tire fitted

Given the lap time as a function of fuel level and tire type, find the minimum time to finish the whole race, subject to one rule:

• Each tire type must be used for at least one lap

The team is free to choose the starting fuel level and the starting tire type at the moment the race begins.

The first line contains an integer $T$, the number of test cases. The race descriptions follow, separated by blank lines.

Each race begins with a line containing two numbers $N$ and $P$ ($1 < N \le 1000$, $0 < P \le 100$).

The next $N$ lines describe the car's performance. Line $i$ (numbered from $1$) contains two numbers $X_i$ and $Y_i$. Here $X_i$ is the time to drive one lap that starts with exactly $i$ units of fuel using tires of the first type, and $Y_i$ is the same value for the second type of tires ($0 < X_i, Y_i \le 1000$). After such a lap the fuel drops to $i-1$.

$N$ is an integer. $P$, $X_i$, and $Y_i$ are real numbers given with exactly three digits after the decimal point.

The car obeys physics: less fuel never makes it slower. Formally, $X_i \le X_{i+1}$ and $Y_i \le Y_{i+1}$ for every $i$ where both sides are defined.

For each race, print on its own line the minimum time to finish that race, with exactly three digits after the decimal point.