题目描述

维克多正在拼接自己的身体…… 现在，他有 $n$ 块从左到右排列的身体碎片，给定长为 $n$ 的数组 $a_1, a_2,\dots, a_n$，表示第 $i$ 块的美观度为整数 $a_i$。 他需要将这些碎片按原顺序划分为恰好 $k$ 个连续段，每块碎片恰好属于一段。每一段组成一个身体部位，该部位的总美观度为段内所有碎片的美观度之和。为了保持身体比例协调，每个部位都必须由至少 $L$ 块、至多 $R$ 块碎片组成。 维克多总是那么万人迷，这归功于他严苛的审美。设从左到右各身体部位的总美观度依次为 $S_1,S_2,\dots,S_k$，他希望下标为奇数的部位总美观度之和减去下标为偶数位置的部位总美观度之和尽可能大，即最大化 $\displaystyle\sum_{i=1}^{k}(-1)^{i+1}S_i$ 由于维克多忙着在野区刷钱，所以这个问题需要你来回答，请你帮他求出这个值的最大值。官方中文

输入格式

第一行包含四个整数 $n,k,L,R\left(1\le k\le n\le 2\times10^5;\,n\times k\le 2\times10^6;\,1\le L\le R\le n\right)$，表示碎片数量、需要划分的连续段数、每段碎片数量的下界、上界。保证至少存在一种合法划分。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n\left(-10^9\le a_i\le10^9\right)$，表示各碎片的美观度。官方中文

输出格式

输出一个整数，表示 $\displaystyle\sum_{i=1}^{k}(-1)^{i+1}S_i$ 的最大值。官方中文