در شهر شانگولیا $n$ اداره دولتی به مردم از طریق وب سایت خود خدمت رسانی می‌کنند. از آن‌جا که همه این ادارات نیازمند دسترسی به اطلاعات شهروندان شانگولیا می‌باشند، شهردار این شهر تصمیم گرفت در سایت مرکزی شهرداری، یک سرور بانک اطلاعاتی شهروندان را راه اندازی نماید و سرور ادارات را از طریق یک بستر شبکه بدان و به یک‌دیگر متصل نماید. این کار از طریق یک شرکت پیمانکاری انجام شد.

هر یک از ادارات برای راه اندازی وب‌سایت خود از یک سرور استفاده کرده‌اند که یک سوکت شبکه دارد و بدان یک کابل شبکه متصل می‌شود. سرور بانک اطلاعاتی شهروندان پیشرفته‌تر است و قابلیت اتصال دو کابل شبکه را دارد.

برای ایجاد این بستر شبکه 2-$n$ سوئیچ مورد استفاده قرار گرفت. هر یک از این سوئیچ‌ها سه سوکت دارد که به هر یک از آن‌ها، سر یک کابل شبکه متصل می‌شود و سوئیچ بسته‌های اطلاعاتی را بر اساس آدرس مقصدشان بین سه پایانه متصل به سوی دیگر کابل‌ها رد و بدل می‌کند. این سه پایانه ممکن است سرور ادارات، سرور بانک اطلاعاتی یا سایر سوئیچ‌ها باشند.

به دلیل رقابت بین ادارات در خدمت‌رسانی به شهروندان، هیچ یک از آن‌ها نمی‌خواهدمدت زمان ارسال بسته‌های اطلاعاتی از سرور بانک اطلاعاتی به سرور آن اداره بیش‌تر از سایر ادارات باشد. لذا ساختا این شبکه به گونه‌ای طراحی گردیده است که مدت زمان ارسال یک بسته اطلاعاتی از سرور بانک اطلاعات مرکزی به سرور تمامی ادارات دقیقا یکسان است. این مدت زمان فقط بر اساس جمع طول کابل شبکه‌ای که بین سرور بانک اطلاعات مرکزی تا سرور یک اداره وجود دارد محاسبه می‌شود، یعنی به ازای اساس جمع طول کابل شبکه‌ای که بین سرور بانک اطلاعات مرکزی تا سرور یک اداره وجود دارد محاسبه می‌شود، یعنی به ازای هر کیلومتر طول کابل شبکه، ۱ میلی ثانیه به مدت زمان عبور بسته اطلاعاتی از آن کابل افزوده می‌شود. فرض کنید طول تمامی کابل‌های شبکه بر اساس کیلومتر عددی صحیح است و زمان لازم برای عبور بسته‌های اطلاعاتی از سوئیچ‌های میانی صفر است.

اکنون پروژه به بهره‌برداری رسیده است و ارتباط تمامی ادارات با سرور بانک اطلاعاتی و با سرور سایر ادارات فراهم گردیده است،‌ اما شهردار معتقد است شرکت پیمانکار طول کابل‌های مورد استفاده در این پروژه را برای دریافت پول اضافه، بیش‌تر از مقدار واقعی گزارش کرده است. او از شما خواسته است جمع طول کابل‌های مورد استفاده رامشخص کنید.

برای این کار مشکل کوچکی وجود دارد، تمامی کابل‌ها از زیر زمین عبور کرده‌اند و شما تنها به سرور ادارات دسترسی دارید. خلاقانه‌ترین کاری که توانستید انجام دهید آن بود که مدت زمان ارسال اطلاعات بین هر جفت از سرور ادارات مختلف را اندازه‌گیری نموده‌اید. حال می‌بایست با استفاده از این اطلاعات مجموع طول کابل شبکه مورد استفاده را محاسبه نمایید.

• در سطر اول ورودی، $n$ آمده است.($3\leq n \leq 1000$)
• در $n$ سطر بعد ماتریس مدت زمان ارسال بسته اطلاعاتی بین هر جفت اداره بر اساس میلی‌ثانیه درج می‌گردد. این ماتریس همواره متقارن خواهد بود.

در تنها سطر خروجی، طول کابل‌های شبکه را بر حسب کیلومتر به صورت یک عدد صحیح در خروجی چاپ نمایید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل