+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در مراکز پردازش کال‍ای دیجی‌کالا، با توجه به سفارشات، بسته‌ها در جعبه‌هایی قرار می‌گیرند تا به مراکز توزیع ارسال شوند و سپس برای مشتریان فرستاده شوند. بخش نگهداری این جعبه‌ها، یک فضای n در m از قفسه‌هاست که هر قفسه شامل چند جعبه است که بر روی هر قفسه، سود و زیان حاصل از فروش کل جعبه‌های آن قفسه مشخص شده‌است. یک ربات هوشمند، با حرکت از خانه‌ی پایین-چپ این جدول و با **تنها حرکات بالا و راست** و با برداشتن تمام جعبه‌های قفسه‌ای که به آن می‌رسد، جعبه‌ها را جمع‌آوری می‌کند و به دست مسئول ارسال به مرکز توزیع می‌رساند. ما نیاز داریم تا این ربات به بهینه‌ترین حالت کار کند و هر بار، از مسیری حرکت کند که مجموع سود و زیان جعبه‌هایی که به دست مسئول مرکز توزیع می‌رسند، بیشینه باشد. به ما کمک کنید تا با توجه به شرایط، بیشترین سود از جمع‌آوری جعبه‌ها، و همچنین مسیری که باید برای جمع‌آوری این جعبه‌ها طی کند را بدست آوریم. # ورودی در ابتدا دو عدد n و m به شما داده‌ می‌شود. سپس در n خط، در هر خط m عدد ورودی داده‌می‌شود که عدد jام ورودی در خط iام همان، نشان‌دهنده تعداد جعبه در آن قفسه است ($a_{i,j}$​). $$1 \le n,m \le 2000$$ $$-10^9 \le a_{i,j} \le 10^9$$ # خروجی در خط اول یک عدد برابر جمع مسیر با بیشترین وزن را خروجی دهید. سپس در خط بعدی رشته‌ای متشکل از کاراکتر‌های `U` و `R` خروجی دهید که هر کاراکتر به ترتیب حرکت مورد نظر را در مسیر بهینه نشان می‌دهد. `U` به معنای **بالا** و `R` به معنای **راست** است. اگر چندین مسیر مطلوب وجود داشت یک مسیر را به دلخواه خروجی دهید. ## ورودی نمونه ۱ ``` 3 3 1 2 3 10 2 1 11 12 1 ``` ## خروجی نمونه ۱ ``` 30 RUUR ``` بهترین مسیر راست-بالا-بالا-راست است که در این مسیر به ترتیب اعداد `11 12 2 2 3` را می‌بینیم. ## ورودی نمونه ۲ ``` 3 4 2 2 2 2 2 2 2 2 2 2 2 2 ``` ## خروجی نمونه ۲ ``` 12 RRRUU ``` در این نمونه، از هر مسیری که حرکت کنیم، مجموع اعداد خانه‌هایی که طی کرده‌ایم برابر ۱۲ می‌شود. پس می‌توان هر مسیر دیگری را نیز چاپ کرد.