스카이랜드

하늘 어딘가에서 KM 왕국이 앞선 기술로 떠 있는 섬 $n$개를 만들었다. 섬에는 $1$번부터 $n$번까지 번호가 붙어 있다.

키타마사 왕은 각 섬의 고도를 음이 아닌 실수 중에서 마음대로 정할 수 있다. 단, 모든 섬의 고도를 더한 값이 $H$ 이상이어야 한다. 섬 $i$를 고도 $h_i$까지 띄우는 비용은 $b_i h_i$이다. 섬끼리는 서로 통신하므로 섬 $i$와 섬 $j$ 사이에 $c_{i,j} |h_i - h_j|$의 비용이 더 든다.

에너지 값이 오른 탓에 왕은 총비용

$\sum_{i=1}^{n} b_i h_i + \sum_{1 \le i < j \le n} c_{i,j} |h_i - h_j|$

을 가장 작게 만들려 한다. 궁정 프로그래머인 당신은 이 최솟값을 구한다. 최솟값은 항상 유리수이다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 정수 $n$과 $H$가 공백 하나로 구분되어 주어진다 ($1 \le n \le 100$, $0 \le H \le 1000$). 둘째 줄에는 정수 $b_1, b_2, \dots, b_n$이 주어진다 ($0 \le b_i \le 1000$). 이어지는 $n$개 줄에는 각각 정수 $c_{i,1}, c_{i,2}, \dots, c_{i,n}$이 주어진다 ($0 \le c_{i,j} \le 1000$). 항상 $c_{i,i} = 0$이고 $c_{i,j} = c_{j,i}$이다.

마지막 테스트 케이스 다음 줄에는 $0$이 두 개 주어진다. 테스트 케이스는 $20$개 이하이다.

각 테스트 케이스마다 Case x: p/q 형식으로 한 줄씩 출력한다. $x$는 $1$부터 세는 테스트 케이스 번호이고, $p/q$는 총비용의 최솟값을 기약분수로 나타낸 것이다. $q > 0$이어야 하고 $p$와 $q$의 최대공약수는 $1$이어야 한다. 최솟값이 정수 $v$이면 v/1로 출력한다. 예를 들어 최솟값이 $2$이면 2/1, $17.5$이면 35/2로 출력한다.