نیروهای جاسوسی «جک گنجشکه» به تازگی خبر از یک حمله عظیم آورده‌اند.

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

خوش‌بختانه، نیروهای جک مکان تمام این $m$ کشتی را ثبت کرده و برای او آورده‌اند. همان‌طور که می‌دانید در دریای کارائیب $n$ جزیره وجود دارد که همه‌ی آن‌ها در تسلط نیروهای جک گنجشکه می‌باشند. جک می‌داند که تا $t$ ساعت بعد با سپاه عظیم خود به این مناطق می‌آید و برای دفاع به نیروهای اعزامی خود ملحق می‌شود. نیروی سپاه عظیم جک آن‌قدر قوی استکه بعد از رسیدن آن، از بابت دفاع مشکلی نخواهد بود. تنها دغدغه‌ی جک، قبل از رسیدن این نیروها می‌باشد.

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

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

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

برنامه‌ای بنویسید که:

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

در سطر اول ورودی، $m،n$ و $t$ آمده است که به ترتیب تعداد جزایر، تعداد کشتی‌های مروارید سیاه و زمان لازم برای رسیدن نیروهای کمکی را مشخص می‌کنند در سطر دوم، $n$ عدد آمده است. عدد $i$ام این سطر، تعداد سربازان اولیه‌ی مستقر در جزیره‌ی $i$ام را مشخص می‌کند. در سطر سوم، $m$ عدد آمده است. عدد $j$ام این سطر، تعداد اولیه‌ی دزدان دریایی کشتی $j$ ام را مشخص می‌کند. سپس در هر یک از $n$ سطر بعدی، دو عدد قرار دارد که به ترتیب مختصات $x$ و $y$ جزیره‌ها را مشخص می‌کند. و در آخر $m$ سطر آمده است که به ترتیب مختصات $x$ و $y$ کشتی‌ها را مشخص می‌کند.(همه اعداد ورودی کم‌تر از ۳۰۰۰۰ است و $1\leq n.m \leq 450$)

در سطر اول خروجی، $S$، کم‌ترین تعداد سرباز مورد نیاز برای اعزام را بنویسید. در سطر دوم، $n$ عدد بنویسید که عدد $i$ام تعداد سربازانی از این $S$ سرباز را نشان می‌دهد که باید به جزیره $i$ ام فرستاده شوند. در سطر سوم، $m$ عدد بنویسید که عدد $j$ام تعداد سربازانی از این $S$ سرباز را نشان می‌دهد که باید به کشتی $j$ ام حمله کنند. در صورت وجود بیش از یک آرایش بهینه برای نیروهای اعزامی، یکی را به دل‌خواه چاپ کنید.

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

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