در یک حرکت، او مجاز است به سلول بعدی به سمت راست یا پایین حرکت کند (حرکت به سمت چپ و بالا ممنوع است).
هنگام عبور از یک سلول، بازیکن به اندازه c.u شارژ می شود.
لازم است حداقل مقدار c.u را پیدا کنید که با پرداخت آن بازیکن می‌تواند به گوشه پایین سمت راست برود.
ورودی:
- خط اول شامل دو عدد N و M - ابعاد جدول (\(1<=N<=20 \)، \(1<=M<=20\));
- سپس خط‌های N از اعداد M در هر کدام وجود دارد - اندازه‌های جریمه در c.u. برای عبور از سلول های مربوطه (هر عدد از 0 تا 100).
خروجی: حداقل مبلغی را که می‌توانید برای دریافت در گوشه پایین سمت راست خرج کنید چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |