포뮬러 레이스

어떤 인기 모터스포츠에서 경주용 자동차는 트랙을 정확히 $N$바퀴 완주해야 합니다. 한 바퀴를 돌 때마다 일정한 양의 연료가 소비되므로, 연료의 양은 앞으로 더 돌 수 있는 바퀴 수로 측정합니다. 탱크에 연료가 $i$만큼 있다는 것은 급유 없이 $i$바퀴를 더 돌 수 있다는 뜻이며, 한 바퀴를 마칠 때마다 연료가 $1$씩 줄어듭니다. 탱크에는 최대 $N$만큼의 연료를 담을 수 있습니다.

한 바퀴를 마친 뒤 자동차는 $P$초 동안 피트 레인에 들를 수 있습니다(들르지 않아도 됩니다). 피트 스톱 동안 정비팀은 다음 작업을 원하는 만큼 수행할 수 있습니다.

• 탱크에 연료를 채운다 (단, $N$을 넘길 수 없다)
• 장착한 타이어의 종류를 바꾼다

팀은 두 종류의 타이어를 사용할 수 있습니다. 한 바퀴의 주행 시간은 다음 두 가지에 따라 달라집니다.

• 현재 탱크에 남아 있는 연료의 양
• 장착한 타이어의 종류

연료량과 타이어 종류에 따른 랩 타임이 주어질 때, 경주 전체를 완주하는 데 필요한 최소 시간을 구하세요. 단, 다음 조건을 지켜야 합니다.

• 두 종류의 타이어를 각각 최소 한 바퀴 이상 사용해야 한다

경주가 시작되는 순간의 연료량과 타이어 종류는 팀이 자유롭게 정할 수 있습니다.

첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 $T$가 주어집니다. 이어서 각 경주에 대한 설명이 빈 줄로 구분되어 주어집니다.

각 경주의 설명은 두 수 $N$과 $P$가 적힌 줄로 시작합니다 ($1 < N \le 1000$, $0 < P \le 100$).

그다음 $N$개의 줄에 자동차의 성능이 주어집니다. $i$번째 줄(1부터 셈)에는 두 수 $X_i$와 $Y_i$가 있습니다. $X_i$는 연료가 정확히 $i$만큼 있는 상태로 시작하는 한 바퀴를 1번 타이어로 달릴 때 걸리는 시간이고, $Y_i$는 2번 타이어에 대한 같은 값입니다 ($0 < X_i, Y_i \le 1000$). 그런 바퀴를 마치면 연료는 $i-1$이 됩니다.

$N$은 정수입니다. $P$, $X_i$, $Y_i$는 소수점 아래 정확히 세 자리까지 주어지는 실수입니다.

자동차는 물리 법칙을 따릅니다. 즉 연료가 적을수록 결코 더 느려지지 않습니다. 식으로 쓰면 양쪽이 모두 정의되는 모든 $i$에 대해 $X_i \le X_{i+1}$, $Y_i \le Y_{i+1}$ 입니다.

각 경주에 대해, 그 경주를 완주하는 최소 시간을 소수점 아래 정확히 세 자리까지 한 줄에 하나씩 출력하세요.