Nekustamais īpašums mežā

Bobs ir ieguvis lielas bagātības no uzvaras "Nim" spēles turnīrā un vēlas uzbūvēt mežā savu muižu. Mežu veido $n$ secīgu laukumu virkne, kas sanumurēti pēc kārtas ar naturāliem skaitļiem, sākot no $1$. Katru laukumu raksturo tā skaistums - $a_i$ ir $i$-tā laukuma skaistums.

Boba muižai jābūt pietiekami lielai, lai tajā varētu glabāt visu viņa bagātību, tāpēc to var būvēt secīgu laukumu segmentā $[l;r]$, kura garums ir vismaz $k$. Segmenta skaistums ir vienāds ar tā laukumu skaistumu summu, proti, segmenta $[l;r]$ skaistums ir vienāds ar $a_l+a_{l+1}+...+a_r$.

Valsts ir atļāvusi Bobam muižu būvēt noteiktā segmentā $[L;R]$, bet Bobs ar to var nebūt apmierināts, tāpēc var izpildīt šādu darbību tik reizes, cik nepieciešams:

• Samaksāt vienu zelta monētu, lai pabīdītu vienu no segmenta galapunktiem pa labi vai pa kreisi par vienu laukumu, neizejot ārpus meža.

Bobs vēlas šādi pārveidot valsts doto segmentu uz tādu, kas būtu pietiekami liels muižas būvniecībai un kura skaistums būtu vislielākais iespējamais, par to samaksājot pēc iespējas mazāk zelta monētu.

Uzrakstiet datorprogrammu, kas palīdz Bobam atrisināt šo uzdevumu!

Pirmajā rindā dots viens naturāls skaitlis $n$ ($n \leq 2 \cdot 10^5$) - laukumu skaits mežā.

Otrajā rindā doti divi veseli skaitļi $L, R$ ($1 \leq L \leq R \leq n$) - valsts atļautais segments.

Trešajā rindā dots naturāls skaitlis $k$ ($1 \leq k \leq n$) - minimālais muižas būvniecībai nepieciešamā segmenta garums.

Ceturtajā rindā doti $n$ veseli skaitļi $a_i$ ($|a_i| \leq 10^9$) - $i$-tā meža laukuma skaistums.

Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddatu vienīgajā rindā jābūt diviem ar tukšumzīmi atdalītiem veseliem skaitļiem: vislielākajam iespējamajam segmenta skaistumam un mazākajam zelta monētu skaitam.