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

یک روز مادر حسن کچل که دیگر از دستش عاصی شده بود، گفت:«حسن تو دیگه برای خودت مردی شدی؛ تا کی می‌خوای این قدر تنبلی کنی؟» و حسن کچل در حالی که سرش را تکان می‌داد گفت «سیب، سیب»؛ فکری به ذهن مادرش خطور کرد: «اگر از این‌جا تا در شهر رو سیب بچینم، حسن دنبال سیب‌ها می‌ره و من می‌تونم در شهر رو روش ببندم.»

در تاریخ آمده که شهر حسن کچل $n$ تا میدون داشته که توی هر میدون یک درخت سیب بوده و بین بعضی از میدون‌ها کوچه بوده. به دلیل بافت قدیمی شهر و کوچه‌های باریک، این کوچه‌ها یک طرفه هستند( حتی برای آدم‌های پیاده)! در زمان اتفاق افتادن داستان روی بعضی از درخت‌ها تعدادی سیب قرار داشته است.

بعد مادر حسن کچل فکر کرد که «برای این کار می‌تونم تعدادی از سیب‌های درخت‌های میدون‌ها رو بچینم و توی بعضی میدون‌هایی که سیب ندارن بگذارم؛ کافیه که یک مسیر که در هر میدونش حداقل یک سیب باشه (چه روی درخت و چه روی زمین) بین میدون کنار خونه و میدون کنار در شهر درست بشه.» و مادر حسن کچل ناراحت شد، چون درخت‌های سیب بلند بودن و با این که پسرش به راحتی ازشون سیب می‌چید ولی این کار برای مادر سخت بود. پس مادر حسن کچل فکر کرد که «باید تعداد سیب‌هایی که می‌چینم رو کمینه کنم.» پس مادر حسن کچل رفت که خباز رو استخدام کنه که سیب‌ها رو براش بچینه، ولی خباز گفت من باید از قبل بدونم که چند تا سیب قراره بچینم.» مادر حسن کچل گشت و گشت تا شما رو پیدا کرد که برایش یک برنامه بنویسید که بگوید دست‌کم چند تا سیب باید چیده شود؛ یک طرفه بودن کوچه‌ها تنها برای حسن مهم است و الا خباز می‌تواند در جهت‌های مختلف از آن‌ها گذر کند.

از این‌جا به بعد داستان در نسخ مختلف دو جور نقل شده:

• در بعضی نسخ آمده که شما به درستی به مادر حسن کچل گفتید که چندتا سیب لازمه بچیند. در نتیجه شما نمره‌ی کامل گرفتید و مادر حسن کچل هم توانست که وی را از شهر بیرون کند. حسن کچل بیچاره هم مجبور شد برود توی جنگل زندگی کند و اسمش شد تارزان.
• در بعضی نسخ هم آمده که شما کمینه‌ی تعداد سیب‌هایی که باید چیده بشود را به درستی نگفتید و مادر حسن کچل نتوانست او را از شهر بیرون کند؛ در نتیجه شما صفر گرفتید.

در سطر ورودی $n$ یعنی تعداد میدان‌های شهر آمده است ($1\leq n \leq 3000$). همان‌طور که می‌توان پیش‌بینی کرد، میدان‌ها از ۱ تا $n$ شماره‌گذاری شده‌اند.

در هر یک از $n$ سطر بعد یکی از این میدان‌ها به این صورت توصیف شده است. اولین عدد تعداد سیب‌های روی درخت این میدان است. دومین عدد تعداد کوچه‌هایی که از این میدان خارج می‌شوند است و بعد از آن شماره‌ی میدان‌هایی که این کوچه‌ها به آن منتهی می‌شود آمده است. تعداد کوچه‌های شهر حداکثر ۵۰۰۰۰ تاست و تعداد سیب‌های موجود بر روی درختان شهر به $2\times 10^9$ نمی‌رسد.

در آخرین سطر ورودی هم به ترتیب شماره‌ی میدان‌های کنار خانه‌ی حسن کچل و کنار در شهر آمده‌اند.

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

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

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