+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو یک ماتریس $2 \times n$ از اعداد طبیعی $M$ دارد. همچنین او تضمین می‌کند که اعداد در هر سطر ماتریس $M$ از یکدیگر متمایز هستند. برای سطر $i$ام از $M$ ($i = 1, 2$)، $s_i$ را برابر بیشترین مجموع اعضا یک زیر دنباله صعودی از اعداد سطر $i$م تعریف میکنیم. به عنوان مثال، اگر $M$ به صورت زیر باشد: \[ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 2 & 3 & 5 & 4 & 1 \\ \end{bmatrix} \] آنگاه $s_1 = 1 + 2 + 3 + 4 + 5 + 6$ و $s_2 = 2 + 3 + 5$ خواهد بود. به ازای هر ماتریس $M$ مجموع $s_1 + s_2$ به عنوان قیمت آن درنظر گرفته می‌شود. پس قیمت ماتریس بالا $31$ است. حال عمو که بسیار تجملاتی است، دوست دارد که ماتریسش بیشترین قیمت را داشته باشد. برای همین او میخواد ترتیب ستون های ماتریسش را به نحوی عوض کند که قیمت ماتریسش بیشینه مقدار ممکن شود. برای مثال، اگر ستون‌های ماتریس مثال قبل $ M = [ c_1, c_2, c_3, c_4, c_5, c_6 ]$ به $ M = [c_2, c_3, c_4, c_5, c_6, c_1] $ تغییر کند، ماتریس جدید به صورت زیر خواهد بود: \[ \begin{bmatrix} 2 & 3 & 4 & 5 & 6 & 1 \\ 2 & 3 & 5 & 4 & 1 & 6 \\ \end{bmatrix} \] و قیمت آن برابر $36$ خواهد بود. یک برنامه بنویسید که به عمو بیشینه قیمت ماتریس را در بین تمام جایگشت‌های ممکن ستون‌های ماتریس $M$ محاسبه کند. ## ورودی - در خط اول ورودی شامل یک عدد طبیعی $n$ است که برابر تعداد ستون‌های ماتریس $M$ است می‌آید. - دو خط بعدی هرکدام شامل $n$ عدد صحیح هستند که عناصر سطر اول و دوم ماتریس $M$ را تشکیل می‌دهند. اعداد داده‌شده در بازه $[1, 50000]$ قرار دارند و در هر سطر اعداد متمایز هستند. ## خروجی یک خط که بیشینه قیمت در بین تمامی جایگشت‌های ممکن ستون‌های $M$ چاپ می‌کند. ## محدودیت‌ها $$1 \leq n \leq 10^4$$ # مثال ## ورودی نمونه ۱ ``` 6 1 2 3 4 5 6 6 2 3 5 4 1 ``` ## خروجی نمونه ۱ ``` 36 ``` ## ورودی نمونه ۲ ``` 5 50 40 3 2 1 1 2 3 100 200 ``` ## خروجی نمونه ۲ ``` 396 ```

حل سؤال در بانک سؤالات