- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
مارکوپولو قصد دیدن دور دنیا در ۸۰ روز را دارد. بنابرین هیچ گاه دوست ندارد شهری را بیشاز یکبار ببیند! به طور دقیقتر هر کشوری که مارکوپولو به آن سفر میکند قابل نمایش به صورت جدولی \(n \times m\) است به طوری که خانههای جدول شهرهای کشور هستند.
سفر مارکو از بالاترین چپترین شهر شروع و به پایینترین راستترین شهر ختم میشود و او پس از اینکه شهری را کامل دید میتواند به یکی از شهرهای مجاور که قبلاً ندیدهاست سفر کند. به دو شهر مجاور میگوییم اگر خانه متناظر آنها در جدول در یک ضلع مجاور باشد.
دیدن هر شهر یک ارزشی دارد و میزان رضایتمندی مارکو از سفر برابر جمع ارزش شهرهای دیدهشده در سفر است. به مارکو بگویید حداکثر رضایتمندیاش از هر سفر چهقدر حداکثر میتواند باشد.
ورودی
در سطر اول ورودی \(t\) تعداد کشورهای مورد گردش مارکو است. سپس اطلاعات \(t\) کشور میآید. \[ 1 \le t \le 10 \, 000 \]
در سطر اول اطلاعات یک کشور به ترتیب \(n\) تعداد سطرها و \(m\) تعداد ستونهای جدول متناظر کشور میآید. \[ 2 \le n, m \le 1000\]
سپس در \(n\) سطر در هر سطر \(m\) عدد میآید که \(j\)امین عدد (از سمت چپ) از سطر \(i\)ام برابر \(c_{i,j}\) ارزش شهر متناظر با خانه سطر \(i\) و ستون \(j\) است. (\(c_{1,1}\) ارزش مبدا و \(c_{n,m}\) ارزش مقصد را نشان میدهد.) \[ 1 \le c_{i,j} \le 10^9\]
تضمین میشود که مجموع \(nm\) برای تمام کشورهای مورد گردش مارکو از ۱۰۰۰،۰۰۰ بیشتر نمیشود. یعنی:
\[ \sum_{i = 1}^{t} n_i \times m_i \le 1000 \, 000\]
خروجی
در \(t\) سطر در هر سطر بیشینه رضایتمندی ممکن برای مارکو از سفر را خروجی دهید. توجه کنید مارکو از شهر مبدا و مقصد هم کاملاً دیدن میکند.
مثال
ورودی نمونه ۱
2
2 2
3 7
5 1
3 3
1 2 4
2 4 8
4 8 16
خروجی نمونه ۱
11
49
در مثال اول کشور به شکل زیر است:
\[ \begin{array}{cc} 3 & 7 \\ 5 & 1 \\ \end{array} \]
دو مسیر زیر بیشتر وجود ندارد:
- \((1, 1) \to (1, 2) \to (2, 2)\)
- \((1, 1) \to (2, 1) \to (2, 2)\)
که حداکثر رضایتمندی برابر \(3 + 7 + 1 = 11\) است.
در مثال دوم کشور به شکل زیر است:
\[ \begin{array}{ccc} 1 & 2 & 4 \\ 2 & 4 & 8 \\ 4 & 8 & 16 \\ \end{array} \]
و مسیر با حداکثر رضایتمندی از مسیر زیر برابر \(49\) میشود. \[(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3)\]