در کشور اژدهاها $n$ شهر و $m$ جاده وجود دارد. شهرها از $1$ تا $n$ شماره‌گذاری شده‌اند و هر جاده دقیقا دو شهر را به هم متصل می‌کند. در مجموع در همه‌ی شهرها $k$ اژدها با نام‌های $D_1, D_2, \ldots, D_K$ در این کشور وجود دارد. اژدهای $D_i$ در ابتدا در شهر $C_i$ زندگی می‌کند و $S_i$ سر دارد. او در هر دقیقه $N_i$ سر جدید تولید می‌کند. یک اژدها تا زمانی که تعداد سرهایش حداقل یک باشد زنده می‌ماند و سرهایش با نرخ گفته شده رشد می‌کند.

می خواهیم تعدادی جنگجو استخدام کنیم تا همه‌ی اژدهاها را بکشیم. هر جنگجو در هر دقیقه یکی از دو کار زیر را می‌تواند انجام دهد ۱) از طریق یکی از جاده‌ها از شهر فعلی به یکی از شهرهای مجاور رود ۲) یکی از سرهای یک اژدهای زنده در شهر فعلی را قطع کند. ما می‌توانیم در هر دقیقه استراتژی اژدهاها را مشخص کنیم. در هر دقیقه بعد از آنکه کار جنگجوها تمام شد، اژدهاهای زنده با نرخ گفته شده سر تولید می‌کنند.

هدف محاسبه کمینه تعداد جنگجوها برای کشتن تمام اژدهاها در یک زمان متناهی است.

ورودی شامل چند سناریو است. خط اول هر سناریو شامل سه عدد $n$، $m$ و $k$ است ($1 \leq n \leq 300$, $0 \leq m \leq N(N-1)/2$, و $1 \leq k \leq 1000$). هر یک از $m$ خط بعد شامل دو عدد $a$ و $b$ ($1 \leq a \neq b \leq n$) است که بیانگر وجود یک جاده بین این دو شهر است. در خط $i$ام از $k$ خط بعد مشخصات اژدهای $i$ام یعنی $C_i$، $S_i$ و $N_i$ آمده است. ورودی با 0 0 0 خاتمه می‌یابد که نیازی به پردازش آن نیست.

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

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

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