یک زندان به شکل یک مربع $N\times N$ است و هر خانه‌ی آن یک سلول زندان است. در هریک از سلول‌ها یک زندانی وجود دارد. یک شبکه‌ی خراب‌کاری می‌خواهد همه‌ی زندانی‌ها را آزاد کند.

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

برنامه‌ای بنویسید که با دریافت اطلاعات مربوط به دیوارها، کم‌هزینه‌ترین پروژه‌ای را بیابد که با آن بتوان تمام زندانی‌ها را به بیرون از زندان رساند. درواقع، باید تعدادی از دیوارها را خراب کرد؛ به‌طوری که هر زندانی بتواند خود را به بیرون دیوارهای زندان برساند.

• در سطر اول ورودی $n$ آمده است.
• در هریک از $n^2$ سطر دیگر چهار عدد آمده است که نشان می‌دهد برای خراب کردنِ دیواری که آن خانه را به خانه‌های مجاورش متصل می‌کند، چه‌قدر است. این چهار دیوار به‌ترتیب، چپ، بالا، راست و پایینِ خانه‌ی مورد نظر قرار دارند. خانه‌ها از بالاترین سطر داده می‌شوند و در هر سطر، از چپ به راست.
• $1 \leq n \leq 1000$

در تنها سطر خروجی، هزینه‌ی بهترین روش را چاپ کنید.

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

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