조깅 코스

조깅을 즐기는 조(Joe)는 매일 아침 동네를 힘차게 달린다. 동네에는 $1$번부터 $n$번까지 번호가 매겨진 집 $n$채가 있으며, 도로로 연결되어 있어 임의의 두 집 사이에는 정확히 하나의 경로만 존재한다. 즉 도로망은 형태를 알 수 없는 하나의 트리를 이루며, $n$개의 잎(leaf) 노드가 각 집이고, 도로가 갈라지거나 합쳐지는 교차로를 나타내는 내부 노드가 최대 $n-1$개(그보다 적을 수도 있음) 있다.

조가 한 집에서 다른 집까지 달릴 조깅 코스를 짜 주자. 베테랑인 조는 코스가 가능한 한 오래 걸리기를 원한다. 도로를 따라 잰 집끼리의 거리(미터) 행렬, 조가 $1$미터를 달리는 데 걸리는 시간 $r$초, 교차로 하나를 지나는 데 걸리는 시간 $t$초가 주어진다. 한 코스의 총 이동 시간은 다음과 같다.

$r \times (\text{코스의 길이, 미터}) + t \times (\text{지나는 교차로 수}).$

총 이동 시간이 가장 긴 집 쌍을 찾아라.

위 그림은 $n = 9$인 경우이다. 번호가 있는 노드는 집, 채워진 노드는 교차로이며, 여러 도로가 한 교차로에서 만날 수 있다. 여기서 $d_{3,9} = 9 + 1 + 7 + 6 = 23$이다. $r = 1$, $t = 5$이면 $3$번 집에서 $9$번 집까지 달리는 데 $1 \times 23 + 3 \times 5 = 38$초가 걸리며, 이것이 이 동네에서 시간상 가장 긴 코스이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수 $n$ ($1 \le n \le 50$, 집의 수), $r$ ($1 \le r \le 10$, $1$미터를 이동하는 데 걸리는 초), $t$ ($1 \le t \le 100$, 교차로 하나를 지나는 데 걸리는 초)가 적힌 한 줄로 시작한다. 이어지는 $n$개의 줄에는 각각 $n$개의 정수가 행 우선(row-major) 순서로 주어지며, $i$번째 줄의 $j$번째 값은 집 $i$와 집 $j$ 사이의 거리 $d_{ij}$이다 ($i \ne j$일 때 $1 \le d_{ij} \le 1000$).

모든 $i$에 대해 $d_{ii} = 0$이고 $i \ne j$일 때 $d_{ij} = d_{ji}$임이 보장된다. 또한 이 행렬은 어떤 올바른 트리의 경로 길이에 대응한다. 즉 어떤 집도 내부 노드와 겹치지 않고, 모든 내부 노드의 차수는 $3$ 이상이며, 모든 간선의 길이는 양수이다. 입력의 끝은 정수 $0$ 하나만 있는 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 가능한 가장 긴 총 이동 시간을 한 줄에 출력한다.