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

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

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