관광 여행

여러분은 어떤 섬에서 하이킹 휴가를 계획하고 있다. 방문할 트랙 $N$ 개를 골랐고, 그 트랙들을 방문할 순서도 이미 정해 두었다. 트랙들은 하나의 원형 여행을 이룬다. 즉, 마지막 트랙을 마치면 다시 첫 번째 트랙으로 돌아온다.

이제 남은 결정은 각 트랙을 어느 방향으로 걸을지이다. 각 트랙에는 시작점(begin)과 끝점(end)이 있으며, 정방향(forward)으로 걸으면 시작점에서 끝점으로, 역방향(backward)으로 걸으면 끝점에서 시작점으로 이동한다. 어떤 트랙도 두 번 걷지 않는다.

각 트랙 $i$ 를 걷는 데에는 방향과 무관하게 $cp_i$ 분이 걸린다. 한 트랙에서 여행 순서상 다음 트랙으로 이동하는 데에는 추가 이동 시간이 든다. 이 시간은 현재 트랙에서 어느 끝점으로 떠나는지와 다음 트랙의 어느 끝점으로 도착하는지에 따라 달라진다. 각 트랙 $i$ 는 다음 트랙으로 가는 네 가지 이동 시간 $cbb$, $cbe$, $ceb$, $cee$ 를 제공한다. 첨자의 첫 글자는 트랙 $i$ 에서 떠나는 끝점(b = 시작점, e = 끝점)을, 둘째 글자는 다음 트랙에서 도착하는 끝점(b = 시작점, e = 끝점)을 뜻한다.

트랙 $i$ 를 정방향으로 걸으면 그 끝점(e)에서 떠나고, 역방향으로 걸으면 시작점(b)에서 떠난다. 다음 트랙을 정방향으로 걸으면 그 시작점(b)에 도착하고, 역방향으로 걸으면 끝점(e)에 도착한다.

모든 트랙의 하이킹 방향을 정하여, 전체 소요 시간(모든 트랙의 길이 합 + 원형 여행 전체의 이동 시간 합)을 최소로 만들고자 한다. 그 최소 소요 시간을 구하시오.

첫째 줄에 테스트 케이스의 개수 $C$ 가 주어진다. ($0 < C \le 100$)

각 테스트 케이스의 첫째 줄에는 두 정수 $N$ 과 $T$ 가 주어진다. $N$ 은 트랙의 개수, $T$ 는 휴가 동안 하이킹에 쓸 수 있는 최대 시간이다. ($1 \le N \le 100,000$, $0 \le T \le 1,000,000$)

이어지는 $N$ 개의 줄에는 각 트랙을 설명하는 다섯 정수 $cp$, $cbb$, $cbe$, $ceb$, $cee$ 가 이 순서대로 주어진다. 트랙들은 방문하는 순서(고정된 여행 순서)대로 나열되므로, 각 줄의 트랙은 바로 다음 줄의 트랙과 이어지고, 마지막 트랙은 다시 첫 번째 트랙과 이어진다(여행은 원형이다). $cp$ 는 트랙의 길이(분)이고, $cbb$, $cbe$, $ceb$, $cee$ 는 위에서 설명한 대로 다음 트랙으로의 이동 시간이다. 주어지는 모든 값은 $1,000,000$ 이하의 음이 아닌 정수이다. 여행 시작 지점까지 차로 가는 시간은 무시한다.

각 테스트 케이스마다 한 줄에 하나씩 출력한다. 방향을 최적으로 선택했을 때 원형 여행을 마치는 데 필요한 최소 전체 소요 시간을 출력한다. 만약 그 최솟값이 $T$ 를 초과하면, 대신 IMPOSSIBLE 을 출력한다.