Trong kì nghỉ hè năm nay Sherry được bố thưởng cho 1 tour du lịch quanh n đất nước tươi đẹp với nhiều thắng cảnh nổi tiếng (vì Sherry đã rất ngoan trong suốt năm học). Tour du lịch này Sherry sẽ được đi bằng máy bay.

Giá vé máy bay từ đất nước i đến đất nước j là Ci,j (chú ý rằng Cij có thể khác Cji ). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng Sherry luôn tiết kiệm và muốn tìm cho mình một hành trình với chi phí rẻ nhất để có thể để dành tiền mua quà về tặng mọi người

Chú ý rằng: Sherry không mất tiền vé khi bay từ nơi mình ở tới quốc gia đầu tiên trong tour du lịch của mình.

Yêu cầu

Bạn hãy giúp Sherry tìm một hành trình đi qua tất cả các nước, mỗi nước đúng 1 lần sao cho chi phí là bé nhất có thể.

Input Specification

Dòng 1 ghi giá trị n là số đất nước (5<n≤10)</p>

Dòng thứ i trong n dòng tiếp theo mỗi dòng gồm n số nguyên, số thứ j là Cị(0<Cij≤10000).</p>

Output Specification

Gồm 1 dòng duy nhất ghi chi phí bé nhất tìm được.