سوسک بزرگ


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

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

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

هر نژاد از سوسک (مانند ii)، چند ویژگی به صورت زیر دارد:

اول aia_i، که اگر به او این تعداد ضربه با دمپایی بزنیم، می‌میرد بدون اینکه سوسک جدیدی از او به وجود بیاید.

دوم bib_i، که اگر به او به این تعداد ضربه با دمپایی بزنیم، می‌میرد اما سوسک‌های جدیدی به وجود می‌آیند.

سوم لیستی از سوسک ها که در صورت مرگ سوسک با bib_i ضربه دمپایی، از او به وجود می‌آیند.

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

ورودی🔗

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

سپس در هر یک از nn سطر بعدی، در سطر ii، توضیحات مربوط به نژاد ii سوسک‌ها به این صورت می‌آید:

ابتدا عدد bib_i می‌آید. سپس عدد aia_i خواهد آمد که توضیح این دو ورودی بالاتر گفته شده است.

سپس یک عدد rir_i می‌آید که نمایانگر تعداد سوسک‌هایی است که از مرگ این سوسک با bib_i ضربه به وجود می‌آید. بعد از آن rir_i عدد متمایز بین ۱ و nn می‌آید که هر کدام نمایانگر این است که در صورت مرگ این سوسک با bib_i ضربه، یک سوسک با این نژاد به وجود می‌آید.

1n200 0001 \le n \le 200\ 000 1ai,bi1091 \le a_i, b_i \le 10^9

مجموع rir_i ها حداکثر برابر 1 000 0001\ 000\ 000 است.

خروجی🔗

در تنها سطر خروجی کمترین تعداد ضربه دمپایی که لازم است تا تمام سوسک‌ها از بین بروند را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1 3 2 1 2
1 1 1 1
1 1 1 2
Plain text

خروجی نمونه ۱🔗

3
Plain text

ورودی نمونه ۲🔗

3
2 7 1 2
2 4 1 3
2 1 1 1
Plain text

خروجی نمونه ۲🔗

5
Plain text

در این نمونه ابتدا سوسک اول را با دو ضربه میکشیم. سپس سوسک از نژاد دوم را با دو ضربه میکشیم و در نهایت سوسک از نژاد سوم که از مرگ سوسک با نژاد دوم به وجود آمده است را با یک ضربه میکشم و هیچ سوسک جدیدی هم از مرگ این سوسک به وجود نمی‌آید.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.