- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در حین تغییر دکوراسیون، همیشه حالتهای جدیدی پیش میآید!
"رادزینکا دوبرامیل ویچشسلافوویچ"
برای مثال، وقتی کوئرا تصمیم گرفت که دکوراسیون خود را تغییر دهد، برای این کار پول لازم داشت و همانطور هم که (ن)میدانید تیم کوئرا حاضر است بمیرد ولی پول برای تغییر دکوراسیون ندهد. از این رو اعضا قرار گذاشتند که با هم بازی رولت روسی را انجام دهند تا پول تغییر جور شود.
بازی رولت روسی (در این سوال) به این صورت انجام میشود که یک تعدادی آدم دور یک دایره نشسته و یک تفنگ را در وسط دایره میگذارند. سپس یکی از اعضا تفنگ را میچرخاند و به سمت هر شخصی که افتاد تمام حساب بانکیاش را خالی و برای تغییر دکوراسیون کنار میگذارند. از طرفی دو نفری که کنار فردی که تفنگ به سمتش است نشستهاند احساس میکنند که شانس آوردهاند که اینبار تفنگ بهشان نیفتاده است و از ترس اینکه نکند دفعهی بعدی بیفتد تمام پولهای داخل حساب خود را به حساب نفر بغلی خود (آنی که تفنگ به سمت او نیست) میدهند.
حال میدانیم که اعضای کوئرا \(n\) نفر میباشند که اگر با شمارههای ۱ تا \(n\) آنها را شمارهگذاری کنیم، نفر \(i\)، به مقدار \(m_i\) ریال پول در حسابش دارد و اعضا هم به ترتیب شماره در کنار هم و دور دایره نشستهاند. (فرد شماره \(n\) کنار فرد شماره ۱ نشسته است.) همینطور میدانیم که قرار است \(k\) بار تفنگ را بچرخانیم. حال بگویید که بیشینه مقداری که میتواند برای تغییر دکوراسیون جمع شود چقدر است. دقت کنید که تفنگ میتواند هر چندبار به یک نفر بیفتد.
ورودی
در سطر اول ورودی دو عدد طبیعی \(n\) و \(k\) آمده است که به ترتیب نمایانگر تعداد افراد و تعداد چرخاندن تفنگ است. سپس در خط بعدی \(n\) عدد آمده است که عدد \(i\)ام نمایانگر مقدار پول اولیه داخل حساب نفر \(i\) یا \(m_i\) میباشد.
\[ 5 \le n \le 2000 \] \[ 1 \le k \le n \] \[ 0 \le m_i \le 1 \ 000 \ 000 \]
خروجی
در تنها سطر خروجی بیشینه مقدار ممکن برای پول بدست آمده برای تغییر دکوراسیون را خروجی دهید.
مثال
ورودی نمونه ۱
5 1
1 2 3 5 4
خروجی نمونه ۱
5
ورودی نمونه ۲
5 2
1 1 1 5 5
خروجی نمونه ۲
11
ورودی نمونه ۳
5 5
1 2 3 4 5
خروجی نمونه ۳
15
ورودی نمونه ۴
5 3
1 1 1 1 1
خروجی نمونه ۴
5