- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برای کنترل جهان باید از کنترل کولر شروع کرد.
«رادزینکا دوبرامیل ویچشسلافوویچ»
با کمک شما در سوال قبل، آقای خطری موفق شد که با اکثریت آرا انتخابات را ببرد و به عنوان مدیر عمارت انتخاب شود. در اولین روز پس از انتخاب، در اولین تصمیم، او کولر خانه را برای همیشه خاموش کرد. سپس به پیدا کردن مشکلات عمارت مشغول شد. در پرسوجوهای اولیهای که انجام داد به این نتیجه رسید که یکی از بزرگترین مشکلات خانه، سوسک بزرگی است که سالهاست در آن خانه زندگی میکند و قصد رفتن از آنجا را ندارد؛ از این رو آقای خطری تصمیم گرفت که برای همیشه از شر این سوسک راحت شود. او برای کشتن این سوسک عجیب دمپایی خاصی از شهر خریده است تا با آن، این سوسک را بکشد. کشتن این سوسک به این راحتیها هم نیست چرا که این با کشتن این سوسک، امکان دارد سوسکهای جدیدی با نژادهای دیگری از دل این سوسک به وجود بیایند. در مجموع میتوان گفت که \(n\) نژاد سوسک وجود دارد که سوسک بزرگ عمارت از نوع اول میباشد.
هر نژاد از سوسک (مانند \(i\))، چند ویژگی به صورت زیر دارد:
اول \(a_i\)، که اگر به او این تعداد ضربه با دمپایی بزنیم، میمیرد بدون اینکه سوسک جدیدی از او به وجود بیاید.
دوم \(b_i\)، که اگر به او به این تعداد ضربه با دمپایی بزنیم، میمیرد اما سوسکهای جدیدی به وجود میآیند.
سوم لیستی از سوسک ها که در صورت مرگ سوسک با \(b_i\) ضربه دمپایی، از او به وجود میآیند.
آقای خطری میخواهد از شر سوسکها راحت شود اما با توجه به زمان محدودی که او دارد و باید به دیگر مشکلات خانه برسد، میخواهد کمترین تعداد ضربه دمپایی را بزند تا از شر تمامی سوسکها راحت شود. به او بگویید که این کمترین تعداد چقدر است تا او بتواند برنامه ریزی کند.
ورودی
در اولین سطر ورودی عدد \(n\) میآید که نمایانگر تعداد نژاد سوسکها میباشد.
سپس در هر یک از \(n\) سطر بعدی، در سطر \(i\)، توضیحات مربوط به نژاد \(i\) سوسکها به این صورت میآید:
ابتدا عدد \(b_i\) میآید. سپس عدد \(a_i\) خواهد آمد که توضیح این دو ورودی بالاتر گفته شده است.
سپس یک عدد \(r_i\) میآید که نمایانگر تعداد سوسکهایی است که از مرگ این سوسک با \(b_i\) ضربه به وجود میآید. بعد از آن \(r_i\) عدد متمایز بین ۱ و \(n\) میآید که هر کدام نمایانگر این است که در صورت مرگ این سوسک با \(b_i\) ضربه، یک سوسک با این نژاد به وجود میآید.
\[1 \le n \le 200\ 000\] \[1 \le a_i, b_i \le 10^9\]
مجموع \(r_i\) ها حداکثر برابر \(1\ 000\ 000\) است.
خروجی
در تنها سطر خروجی کمترین تعداد ضربه دمپایی که لازم است تا تمام سوسکها از بین بروند را چاپ کنید.
مثال
ورودی نمونه ۱
3
1 3 2 1 2
1 1 1 1
1 1 1 2
خروجی نمونه ۱
3
ورودی نمونه ۲
3
2 7 1 2
2 4 1 3
2 1 1 1
خروجی نمونه ۲
5
در این نمونه ابتدا سوسک اول را با دو ضربه میکشیم. سپس سوسک از نژاد دوم را با دو ضربه میکشیم و در نهایت سوسک از نژاد سوم که از مرگ سوسک با نژاد دوم به وجود آمده است را با یک ضربه میکشم و هیچ سوسک جدیدی هم از مرگ این سوسک به وجود نمیآید.