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

برای کنترل جهان باید از کنترل کولر شروع کرد.

«رادزینکا دوبرامیل ویچشسلافوویچ»

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

نقشه‌ی عمارت به صورت یک جدول $n \times m$ می‌باشد که در بعضی از خانه‌های این جدول استخر نیز وجود دارد. در این عمارت از یک خانه می‌توان به یکی از خانه‌های چپ، بالا، راست و یا پایین آن خانه (در صورت وجود) رفت و این کار به اندازه‌ی یک شتیل برای آقای خطری خرج دارد؛ یعنی او باید به آقای برداری برای این جابجایی یک شتیل بدهد. همچنین مسئول هر استخر در صورتی که آقای برداری آقای خطری را به آن استخر بیاورد حاضر است مقداری شتیل به آقای برداری بدهد.

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

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

ورودی

در سطر اول ورودی دو عدد $n$ و $m$ آمده است که نمایانگر ابعاد عمارت می‌باشند.

سپس در $n$ سطر، در هر سطر $m$ عدد می‌آید که عدد $j$ در سطر $i$، $h_{i,j}$ بوده و نمایانگر عمق استخر موجود در خانه‌ی $(i, j)$ جدول می‌باشد. دقت کنید که اگر عمق استخری ۰ باشد، به این معنی است که دیگر آنجا استخری نیست و درنتیجه آنجا استخری وجود ندارد که بتوان از آن دیدن کرد.

بعد از آن در $n$ سطر، در هر سطر $m$ عدد می‌آید که عدد $j$ در سطر $i$، $c_{i,j}$ بوده و نمایانگر مقدار شتیلی است که مسئول آن استخر (در صورت آوردن آقای خطری) به آقای برداری می‌دهد.

$$1 \le n, m \le 1\ 000$$ $$0 \le h_{i, j} \le 1\ 000\ 000$$ $$0 \le c_{i, j} \le 1\ 000\ 000$$

خروجی

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

مثال

ورودی نمونه ۱

2 2
1 2
3 4
2 2
2 2

خروجی نمونه ۱

12

ورودی نمونه ۲

3 3
1 2 3
3 2 1
2 3 1
1 4 5
5 4 1
4 5 1

خروجی نمونه ۲

17

در این نمونه ابتدا به استخر در خانه‌ی (2,3) رفته، سپس به ترتیب به سراغ استخر‌های خانه‌های (3,1) و (1,3) میرویم. هزینه‌ی جابجایی ۷ و پولی که مسئولین استخر می‌دهند ۱۰ خواهد بود که در مجموع ۱۷ می‌شود.