+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون مقدماتی دوم دوره ۲۶ المپیاد کامپیوتر ---------- مورتی بار دیگر در یک ماجراجویی خطرناک با پدربزرگ دانشمندش ریک همراه شده تا از یک نانوایی معروف به نام «سلری» برای صبحانه نان تهیه کنند. این نانوایی در دنیای دوردستی واقع شده است که ساکنان بی‌حوصله‌ای دارد. آن‌ها تا زمانی که حوصله‌شان به سر نیامده موجودات مهربانی هستند، اما به محض این که حوصله‌شان سر برود تبدیل به موجودات بی‌رحمی می‌شوند و هر چیزی در اطرافشان باشد را به آتش می‌کشند. «آقای میسیک»، صاحب نانوایی سلری، که از دوستان قدیمی ریک و مورتی است، امروز دست‌تنها است و مشتری‌های زیادی در صف نانوایی منتظر نان‌شان هستند. او با دیدن ریک و مورتی بسیار خوش‌حال می‌شود و از آن‌ها می‌خواهد در امر خطیر نان‌پزی کمکش کنند. آن‌ها به این شکل تقسیم وظیفه می‌کنند که ریک و آقای میسیک نان‌ها را بپزند و مورتی نان‌ها را بین مشتری‌ها پخش کند. طبق معمول مشتری‌ها در $n$ صف مختلف در نانوایی ایستاده اند. مورتی هر نانی را که به دستش می‌رسد را می‌تواند به یکی از مشتری‌هایی که در سر یکی از صف‌ها ایستاده است بفروشد. به بیان دیگر او هر بار یکی از $n$ صف را انتخاب می‌کند و به مشتری‌ای که در جلوی آن صف ایستاده نان می‌فروشد. هر مشتری دقیقاً به یک عدد نان نیاز دارد و بعد از خرید نان از صف خارج می‌شود و مغازه را ترک می‌کند. آقای میسیک و ریک با کمک یک‌دیگر می‌توانند با سرعت یک نان بر ثانیه نان بپزند. از طرفی، هر مشتری یک میزان حوصله‌ای دارد که برای مشتری $j$ ام در صف $i$ ام آن را با $p_{i,j}$ نشان می‌دهیم. در صورتی که این مشتری تا $p_{i,j}$ ثانیه بعد از شروع به کار ریک و مورتی نان نخرد، نانوایی را به آتش می‌کشد.  در صورت آتش گرفتن مغازه ریک و مورتی می‌توانند با استفاده از دستگاه تله‌پورت فرار کنند و هیچ آسیبی نبینند. اما مورتی از کار نان فروشی لذت می‌برد و دوست دارد تا قبل از آتش گرفتن مغازه یا تمام شدن مشتری‌ها، به بیشترین تعداد مشتری ممکن نان بفروشد. مورتی حداکثر چند نان می‌تواند بفروشد؟ دقت کنید که بعد از شروع به کار ریک و مورتی مشتری دیگری وارد مغازه نخواهد شد. # ورودی در خط اول ورودی $n$، تعداد صف‌های نانوایی، آمده است. در $n$ خط بعدی در هر خط ابتدا یک عدد طبیعی $l_i$ آمده است که نشان‌دهنده‌ی طول صف $i$ ام است. در ادامه‌ی خط $i$ ام، $l_i$ عدد طبیعی آمده است که نشان‌دهنده‌ی $p_{i,1}, p_{i,2}, ..., p_{i,l_i}$، میزان حوصله‌ی مشتری‌های صف $i$ است. $$ 1 \le n \le \sum_{i=1}^n{l_i} \le 100 \ 000 $$ $$ 1 \le p_{i,j} \le 10^9 $$ # خروجی در تنها خط خروجی بیشترین تعداد مشتری‌هایی که مورتی می‌تواند به آن‌ها نان بفروشد را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۷ | ۱۰ | $ \sum_{i=1}^n{l_i} \le 10 $ | | ۲ | ۱۸ تا ۳۵ | ۲۰ | $ \sum_{i=1}^n{l_i} \le 1\ 000 ,n\le2 $ | ۳ | ۳۶ تا ۸۵ | ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 1 1 2 9 2 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 3 2 1 2 2 3 5 1 4 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 3 1 3 1 4 2 5 2 ``` ## خروجی نمونه ۳ ``` 4 ```