Հաշվողական համակարգի հզորություն

Հաշվողական համակարգը բաղկացած է $n$ հատ հաջորդաբար իրար միացված հանգույցներից։ Յուրաքանչյուր հանգույց բնութագրվում է $h_i$ հաշվարկային հզորությունով։ Հաշվողական համակարգի ընդհանուր հզորությունը հավասար է հանգույցների հաշվարկային հզորությունների գումարին։

Համակարգի ճարտարապետը ցանկանում է ընտրել որոշակի հանգույց և տարածել նրա ազդեցությունը $k$ հարևան հանգույցների վրա՝ մեկ ուղղությամբ և մյուս ուղղությամբ։ Եթե որևէ ուղղությամբ հանգույցները $k$ -ից պակաս են, ապա նա ազդեցությունը կտարածի այնքան հանգույցների վրա, որքան կա։ Ենթադրենք, որ նա տարածել է ընտրված հանգույցի ազդեցությունը ընդհանուր առմամբ $d$ հանգույցների վրա։ Այդ դեպքում ընտրված հանգույցի հաշվարկային հզորությունը կդառնա $(1 + d) \cdot h_i$ , իսկ այն հանգույցների հաշվարկային հզորությունը, որոնց վրա տարածվել է նրա ազդեցությունը, կլինի $0$ ։

Օգնեք համակարգի ճարտարապետին հասկանալու, թե նշված գործողության միջոցով ինչ մեծագույն արժեքի կարելի է հասցնել հաշվողական համակարգի ընդհանուր հզորությունը։

Մուտքային տվյալները

Առաջին տողում տրված են $n$ և $k$ ամբողջ թվերը՝ հանգույցների քանակը, և թե քանի հանգույցի վրա է տարածվում վերևում նկարագրված գործողությունը:
Երկրորդ տողում տրված են հանգույցների $h_0, h_1, \ldots, h_{n - 1}$ հզորությունները։

Ելքային տվյալները

Ելքում պետք է արտածել մեկ թիվ՝ հաշվողական համակարգի առավելագույն հնարավոր հզորությունը նշված գործողության կիրառման դեպքում։

Օրինակներ

Մուտք	Ելք
`3 1 2 3 1`	`9`
`8 3 1 2 3 4 3 2 1 5`	`33`

Ենթախնդիրները

Համար	Սահմանափակումներ	Միավոր
$0$	Օրինակները	$0$
$1$	$n \leq 3$	$6$
$2$	$n \leq 6$	$12$
$3$	$k = 0$	$7$
$4$	$n, k \leq 1000$	$20$
$5$	Լրացուցիչ սահմանափակումներ չկան։	$55$

Եթե ենթախնդրում տարրի համար սահմանափակում նշված չէ, ապա տեղի ունեն հետևյալ սահմանափակումները․

$1 \leq n \leq 2 \cdot 10^5$ ,
$0 \leq k \leq 2 \cdot 10^5$ ,
$0 \leq h_i \leq 5\cdot10^5\ (1 \leq i \leq n)$ :

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB