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

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

شرایط قرار گرفتن جومونگ و همراهانش به صورت یک جدول $n \times m$ است که جومونگ و همه سپاهش در بالاترین خانه سمت چپ و امپراطور در پایین سمت راست.

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

چون جومونگ و افرادش در هر دقیقه می‌توانند یک خانه را در $4$ جهت اصلی طی کنند (سواره‌نظام هم به دلیل سنگینی سلاحش همین سرعت را دارد). جومونگ می‌داند که باید حداقل زمان ممکن را تلف کنند تا هم امپراطور نتواند آمادگی برای مقابله داشته باشد و هم همه هم‌زمان با هم برسند. برای همین یک قانونی جومونگ می‌گذارد که همه باید یا سمت راست یا پایین بروند. در لحظه $0$ همه نیروهای سواره‌نظام لازم برای له کردن نیروهای بیرون قلعه را می‌فرستد و در لحظه $1$ بقیه نیروها را می‌فرستد.

به جومونگ برای حساب کردن حداقل تعداد نیروهای سواره‌نظام کمک کنید. نکته مهم این است که چند نیرو می‌توانند با هم در یک نقطه بایستند.

• در سطر اول ورودی $n$، $m$ و $k$ به ترتیب بیانگر تعداد سطرهای ورودی و ستون‌های ورودی و تعداد سربازان هستند.
• در $k$ سطر بعدی، در هر سطر دو عدد $x$ و $y$ که به ترتیب بیانگر سطر و ستون سرباز هستند می‌آید.

در تنها سطر خروجی حداقل تعداد سربازهای مورد نیاز را بنویسید.

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

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