Skyland

Somewhere in the sky the KM kingdom built $n$ floating islands with its advanced technology. The islands are numbered from $1$ to $n$.

King Kitamasa picks the altitude of every island freely among the non-negative real numbers, as long as the altitudes add up to at least $H$. Lifting island $i$ to altitude $h_i$ costs $b_i h_i$. The islands also talk to each other, so island $i$ and island $j$ cost another $c_{i,j} |h_i - h_j|$.

Energy prices went up, so the king wants the total cost

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

to be as small as possible. You are the court programmer, so compute that minimum. It is always a rational number.

The input holds several test cases. The first line of a test case has two integers $n$ and $H$ separated by one space ($1 \le n \le 100$, $0 \le H \le 1000$). The second line has $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 1000$). Each of the next $n$ lines has $n$ integers $c_{i,1}, c_{i,2}, \dots, c_{i,n}$ ($0 \le c_{i,j} \le 1000$). Always $c_{i,i} = 0$ and $c_{i,j} = c_{j,i}$.

A line with two zeros follows the last test case. There are at most $20$ test cases.

For each test case print one line in the form Case x: p/q. Here $x$ is the test case number counting from $1$, and $p/q$ is the minimum total cost written as a reduced fraction, with $q > 0$ and $\gcd(p, q) = 1$. An integer minimum $v$ is printed as v/1. For example, a minimum of $2$ is printed as 2/1 and a minimum of $17.5$ is printed as 35/2.