یه اتوبوس هست که مسافرها رو جابه‌جا می‌کنه که ماله داش ممد. این اتوبوس به دلایل جنبی خیلی شلوغ، در عقبشم جدیدا خراب شده و فقط یه در داره، صندلی هم فکر نکنم از اولش داشته چون نگاش که می‌کنی فقط یه راهروی درازه که جا واصه واستادن $L$ نفر داره. یادم رفت، یه مشکل کوچیکم داره، چون یکم تنگه وقتی یکی می‌خواد پیاده شه همه‌ی جلوییاش هم مجبور می‌شن پیاده شن (البته طوری نیست می‌تونن دوباره سوار شن فقط بیاد بلیط بدن!)، اگرم کسی بخواد سوار شه باید جلوتر از همه وایسه (البته بازم طوری نیست اگه اسرار داشته باشه جای $k$ ام از آخر وایسه آدمایی که تا جای $k$ ام از آخر وایسادن می‌تونن پیاده شن و بعد دوباره سوار شن فقط بازم باید بلیط بدن!)

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

تو این شهر $N$ ایستگاهه که داش ممد هر روز صبح از اولی شروع می‌کنه و تا آخری به ترتیب می‌ره و وقتی به آخری می‌رسه دیگه شب شده و می‌ره خونشون می‌خوابه و فردا دوباره روز از نو و روزی از نو. در ضمن تو شهر $a_{ij}$ آدم هست که هر روز با این اتوبوس از ایستگاه $i$ به ایستگاه $j$ می‌ره و البته به خاطر شرایط اتوبوس احتمالا تو بعضی ایستگاه‌های بین $i$ و $j$ پیاده و دوباره سوار می‌شه. بدیهی که $\forall_{i,j} N \Rightarrow i >= j>0 \Rightarrow a_{ij} =0$ و همچنین می‌دونیم که $\forall_{i,j}0<i<j \Leftarrow N \Rightarrow 0 < a_{ij} \Leftarrow 1000$. حالا شما باید بفهمید که اگه مسافرها نهایت هوش رو به‌کار ببرن و با هم همکاری کنن تا در مجموع کم‌ترین تعداد بیلیط رو به داش ممد بدن حداقل چند تا بلیط گیره داش ممد میاد. در ضمن توجه کنید که $L>= \sum_{i,j} a_{ij}$ یعنی اتوبوس داش ممد به اندازه‌ی کافی جا داره پس شما نیازی به دونستن $L$ ندارید.

در خط اول $N$ آمده است. $( N \Leftarrow 1000)$

در خطوط ۲ تا $N+1$: در خط $i+1$ به ترتیب $a_{i1}$ تا $a_{iN}$ آمده‌اند.

در یک سطر حداقل تعداد بلیط‌هایی که گیر داش ممد می‌آید را بنویسید.

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