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

---

ابواسحاق پس از ترمیم رشتهٔ افکار خود، آغاز به کشت خیار کرد! امّا در این بین، علف‌های هرز مانع کسب و کار او شدند. برای همین، شروع به حذف کردن علف‌های هرز کرد.

مزرعهٔ او به شکل جدولی \(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)\) موجود است) سپس تمامی آنها را با دست می‌کند که در مجموع از او ۸ واحد انرژی می‌گیرد همچنین می‌توان ثابت کرد این مقدار کمینه انرژی لازم است.