+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ابواسحاق پس از ترمیم رشتهٔ افکار خود، آغاز به کشت خیار کرد! امّا در این بین، علف‌های هرز مانع کسب و کار او شدند. برای همین، شروع به حذف کردن علف‌های هرز کرد. مزرعهٔ او به شکل جدولی $n\times m$ است که دارای $n$ سطر با شماره‌های $0$ تا $n - 1$ از بالا به پایین و $m$ ستون با شماره‌های $0$ تا $m - 1$ از چپ به راست می‌باشد. در ابتدا $k$ علف هرز در مزرعه وجود دارد. او در هر مرحله می‌تواند یکی از عملیات‌های زیر را انجام دهد: + یک علف‌ هرز از خانهٔ $(i, j)$ را با دست بکَنَد. در این صورت $w_{i, j}$ انرژی مصرف می‌کند. (برای خم شدن و کندن علف هرز) + پا روی خانهٔ $(i, j)$ بگذارد، در این صورت یکی از علف‌های هرز موجود در آن خانه از بین رفته و یک علف هرز به خانه‌ی $((i + 1)\mod n, j)$ و علف هرزی دیگر به خانه‌ی $(i, (j + 1)\mod m)$ اضافه می‌شود. توجه کنید که در این عملیات هیچ انرژی‌ای از او کم نمی‌شود ($a\mod b$ برابر با باقی مانده تقسیم $a$ بر $b$ است). حال او وضعیت اولیهٔ مزرعه و علف‌های هرز را به شما می‌دهد و از شما می‌خواهد که کمترین انرژی لازم برای از بین بردن تمامی علف‌های هرز مزرعه را محاسبه کنید. # ورودی در خط اول دو عدد $n$ و $m$ و $k$ داده می‌شود. در هر یک از $n$ سطر بعدی $m$ عدد آمده است که عدد $j$ ام در سطر $i$ ام مقدار $w_{i, j}$ را مشخص می‌کند. در خط $i$ ام از $k$ خط بعدی دو عدد $x_i$ و $y_i$ آمده که نشان می‌دهد علف هرز $i$ ام در خانه $(x_i, y_i)$ است. $$ 1 \le n, m \le 1\ 000 $$ $$1 \le k \le 1\ 000$$ $$ 0 \le x_i < n $$ $$ 0 \le y_j < m $$ $$ 1 \le w_{i, j} \le 1\ 000$$ **دقت کنید ممکن است در ابتدا در یک خانه بیش از یک علف هرز وجود داشته باشد.** # خروجی در یک خط عدد خواسته شده را چاپ کنید. ## ورودی نمونه ۱ ``` 2 2 1 3 1 1 1 0 0 ``` ## خروجی نمونه ۱ ``` 2 ``` در ابتدا یک علف هرز در خانهٔ $(0 ,0)$ وجود دارد. ابواسحاق روز آن پا گذاشته و در نتیجه در هر یک از خانه‌های $(1 ,0)$ و $(0 ,1)$ یک علف هرز بوجود می‌آید. سپس هر کدام از علف‌های هرز جدید را با دست می‌کند و در مجموع ۲ واحد انرژی از دست می‌دهد. ## ورودی نمونه ۲ ``` 3 3 2 7 5 1 4 3 1 1 2 1 0 1 1 0 ``` ## خروجی نمونه ۲ ``` 8 ``` در ابتدا دو علف هرز یکی در خانه $(0,1)$ و دیگری در خانه $(1,0)$ موجود است، ابواسحاق با پا گذاشتن روی این دو علف آنها را به صورت $(0,2)$، $(1,1)$، $(1,1)$ و $(2,0)$ درمی‌آورد (توجه کنید دو علف هرز در خانه $(1,1)$ موجود است) سپس تمامی آنها را با دست می‌کند که در مجموع از او ۸ واحد انرژی می‌گیرد همچنین می‌توان ثابت کرد این مقدار کمینه انرژی لازم است.

حل سؤال در بانک سؤالات