فهرست مندرجات
Toll
به خاطر رشد روزافزون راه‌زنی در جاده ابریشم، تعداد بازرگانانی که از این جاده عبور می‌کند کم و کم‌تر می‌شود. هر راه‌زنی در هر نقطه از جاده به هر میزان که ممکن باشد از بازرگانان پول اخاذی می‌کند. به همین خاطر، بازرگانان ترحیج می‌دهند از مسیر دیگری مسافرت کنند حتی اگر طول مسیرشان طولانی‌تر شود. این موضوع باعث کاهش درآمد راه‌زن‌ها شده است. به همین خاطر مرادبیگ، ریس راه‌زن‌ها، مجبور به طراحی یک سیستم راه‌زنی جدید به نام سیستم عوارض شده است. براساس این سیستم، هر راه‌زن محدود به یک ناحیه‌ی مربع شکل (شامل مرزها) خاص خود شده است که به آن حوزه استحفاظی آن راه‌زن می‌گویند. حوزه‌های استحفاظی می‌توانند با هم اشتراک داشته باشند. مهم‌تر آنکه میزان عوارض دریافتی در هر حوزه استحفاظی یک اشلوب در نظر
گرفته شده است. دیگر قوانین سیستم جدید در زیر امده است.
- یک راه‌زن خارج از حوزه استحفاظیش نمی‌تواند عوارض بگیرد.
- هر راه‌زن به محض دریافت عوارض از یک بازرگان باید یک روادید (بلیط عبور) برای آن بازرگان صادر کند که فقط مخصوص حوزه استحفاظی اوست. این روادید به بازرگان اجازه می‌دهد آزادنه داخل حوزه استحفاظی آن راه‌زن بدون پرداخت عوارض بیشتر به دیگر راه‌زن‌ها مسافرت کند. به محض آنکه بازرگان از حوزه استحفاظی آن راه‌رن خارج شود روادید باطل شده و دیگر اعتباری ندارد.
- بدون روادید معتبر، یک بازرگان نمی‌تواند داخل حوزه استحفاظی راه‌زن‌ها مسافرت کند.
- اگر یک بازرگان علاقمند باشد می‌تواند روادید فعلی خود را باطل و روادید یک راه‌زن دیگر را که در حوزه استحفاظی او قرار دارد را دریافت کند. البته بازرگان طبق قانون باید یک اشلوب برای روادید جدید پرداخت کند.
مارکو پلو که تاجر ثروتمندی است می‌خواهد جاده ابریشم را از ابتدا تا انتها طی کند. هر چند با وضع سیستم جدید اوضاع بسیار بهتر از گذشته است اما هم‌چنان مارکو پلو به فکر پرداخت عوارض کم‌تر است. حال شما باید برنامه‌ای بنویسید که کمینه عوارضی که مارکوپلو باید پردادخت کند را محاسبه کند. برای سادگی می‌توانید فرض کنید که جاده ابریشم از ضلع‌ها‌ی افقی و عمودی تشکیل شده است.
ورودی
ورودی شامل چندین سناریو است. خط اول هر سناریو شامل دو عدد صحیح و مثبت $n$ و $m$ است ($n,m \leq 1000$) که به ترتیب تعداد حوزه‌های استحفاضی و تعداد راس‌های جاده ابریشم را مشخص می‌کنند. در هریک از $n$ خط بعد، مشخصات یک حوزه استحفاظی می‌آید. هر خط شامل سه عدد صحیح و مثبت $x$، $y$ و $k$ ($x, y \leq 10^6, k\leq 1000$) است که $x$ و $y$ گوشه سمت چپ و پایین حوزه استحفاظی را نشان می‌دهد و $k$ طول ضلغ حوزه استحفاظی را نشان می‌دهد. مختصات رئوس جاده ابریشم به ترتیب از ابتدا تا انتها در $m$ خط بعد ظاهر می‌شوند. تضمین می‌شود که جاده ابریشم داده شده خودش را قطع نمی‌کند. ورودی با 0 0 خاتمه می‌یابد که نیازی به پردازش آن نیست.
خروجی
به ازای هر سناریو، کمینه عوارضی که مارکو پلو باید پرداخت کند را در یک خط چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت