Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong một thị trấn nhỏ, các ngôi nhà đều có đường nối ra điểm giao sau đó từ điểm giao đi đến các ngôi nhà khác. Ví dụ sơ đồ các ngôi nhà (được đánh số) và các điểm giao (chấm tròn đen) có thể như sau:

Ở mỗi đoạn đường có giá trị trọng số là độ dài (tính theo mét) giữa mỗi nhà đến các điểm giao. Một người có ý định đi lang thang trong thị trấn từ ngôi nhà này đến một ngôi nhà khác, càng lâu càng tốt. Giả sử không có hai ngôi nhà nào nối trực tiếp đến nhau, và biết khoảng thời gian người đó đi được 1 mét đường và thời gian cần thiết để người đó đi qua một điểm giao cắt, hãy xác định khoảng thời gian dài nhất có thể cần thiết để đi từ nhà này đến nhà khác.

Ví dụ trong sơ đồ hình trên, cặp xa nhất sẽ là d3,9 = 9+1+7+6 = 23.

Biết người đó đi 1 mét mất 1 giây và đi qua một điểm giao mất 5 giây thì tổng thời gian dài nhất sẽ là: 1 × 23 + 3 × 5 = 38 giây.

Input

Có nhiều bộ test. Mỗi bộ test gồm:

• Một dòng ghi ba số n, r, t với  n là số ngôi nhà (1<=n<=50), r là thời gian cần để đi một mét đường (1<=r<=10), t là thời gian để đi qua một điểm giao cắt (1<=t<=100).
• n dòng tiếp theo, mỗi dòng có n giá trị d_ij ghi khoảng cách từ mỗi cặp hai ngôi nhà (1<=d_i,j<=1000). Ma trận khoảng cách được đảm bảo đối xứng (d_ij = d_ji).
• Đầu vào kết thúc với một dòng ghi duy nhất một số 0.    

Output

Với mỗi bộ test, in ra màn hình trên một dòng khoảng thời gian dài nhất có thể.

Example

Input:

9 1 5
0 8 22 16 16 13 24 14 11
8 0 20 14 14 11 22 12 9
22 20 0 12 12 11 22 12 23
16 14 12 0 4 5 16 6 17
16 14 12 4 0 5 16 6 17
13 11 11 5 5 0 13 3 14
24 22 22 16 16 13 0 14 25
14 12 12 6 6 3 14 0 15
11 9 23 17 17 14 25 15 0
0

Output:

38